Rearrange Last N

Problem

Note: Try to solve this task in O(list size) time using O(1) additional space, since this is what you’ll be asked during an interview.

Given a singly linked list of integers l and a non-negative integer n, move the last n list nodes to the beginning of the linked list.

Example

For l = [1, 2, 3, 4, 5] and n = 3, the output should be
solution(l, n) = [3, 4, 5, 1, 2];
For l = [1, 2, 3, 4, 5, 6, 7] and n = 1, the output should be
solution(l, n) = [7, 1, 2, 3, 4, 5, 6].

Solution

// Singly-linked lists are already defined with this interface:
// type ListNode struct {
//   Value interface{}
//   Next *ListNode
// }
//
func solution(l *ListNode, n int) *ListNode {
    if l == nil || l.Next == nil || n == 0 {
        return l
    }

    // Count the length of the list
    length := 1
    lastNode := l
    for lastNode.Next != nil {
        length++
        lastNode = lastNode.Next
    }

    // Handle edge cases
    n = n % length
    if n == 0 {
        return l
    }

    // Find the new head and tail of the list
    newTail := l
    for i := 1; i < length-n; i++ {
        newTail = newTail.Next
    }
    newHead := newTail.Next

    // Update pointers
    lastNode.Next = l
    newTail.Next = nil

    return newHead
}