I am struggling to understand given the below solution how the first half of the linked list is joined to the back end. I've ran through it logically but cannot understand the referencing of the last 3 lines.
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.
For example, for the inputs l = [1, 2, 3, 4, 5]
and n = 3
, the output of rearrangeLastN(l, n)
should be
[3, 4, 5, 1, 2]
.
// Singly-linked lists are already defined with this interface:
// class ListNode<T> {
// ListNode(T x) {
// value = x;
// }
// T value;
// ListNode<T> next;
// }
//
ListNode<Integer> rearrangeLastN(ListNode<Integer> l, int n) {
if (l == null || n == 0) return l;
ListNode<Integer> fast = l; //1,2,3,4,5
ListNode<Integer> slow = l; //1,2,3,4,5
while(n > 0 && fast != null) { //3->2->1
fast = fast.next; //4->5
n--; //1
}
if (n >= 0 && fast == null) return l;
while (fast.next != null) { //1 Interation (4->5->null)
slow = slow.next; //2->3->4->5
fast = fast.next; //5
}
ListNode newHead = slow.next; //3->4->5
slow.next = null;
fast.next = l;
return newHead;
}
Initially:
1 -> 2 -> 3 -> 4 -> 5 -> null
^
l
fast
slow
After the 1st while
loop:
1 -> 2 -> 3 -> 4 -> 5 -> null
^ ^
l
fast
slow
After the 2nd while
loop:
1 -> 2 -> 3 -> 4 -> 5 -> null
^ ^ ^
l
fast
slow
After the line ListNode newHead = slow.next;
:
1 -> 2 -> 3 -> 4 -> 5 -> null
^ ^ ^ ^
l
fast
slow newHead
After the line slow.next = null;
:
1 -> 2 -> null 3 -> 4 -> 5 -> null
^ ^ ^ ^
l
fast
slow newHead
After the line fast.next = l;
:
┌────────────────────────────────┐
└> 1 -> 2 -> null 3 -> 4 -> 5 ┘
^ ^ ^ ^
l
fast
slow newHead