Rearrange Last N

Rearrange Last N

February 28, 2023

Moch Lutfi
Name
Moch Lutfi
Twitter
@kaptenupi

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
}