Search code examples
javadata-structuresnodes

rearrangeLastN - Java


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;
}

Solution

  • 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