Rearrange Last N
February 28, 2023
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]
andn = 3
, the output should be
solution(l, n) = [3, 4, 5, 1, 2]
; - For
l = [1, 2, 3, 4, 5, 6, 7]
andn = 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}