How does this Linked list Sort solution work?

Question

Im working on some leetcode question and I dont understand this solution and cant find an answer there so I need some clarification please. The quesition is to sort a linked list. This solution uses a merge sort approach. The solution is below

class Solution {
public ListNode sortList(ListNode head) {
    if (head == null || head.next == null)
        return head;
    ListNode mid = getMid(head);
    ListNode left = sortList(head);
    ListNode right = sortList(mid);
    return merge(left, right);
}

ListNode merge(ListNode list1, ListNode list2) {
    ListNode dummyHead = new ListNode();
    ListNode tail = dummyHead;
    while (list1 != null && list2 != null) {
        if (list1.val < list2.val) {
            tail.next = list1;
            list1 = list1.next;
            tail = tail.next;
        } else {
            tail.next = list2;
            list2 = list2.next;
            tail = tail.next;
        }
    }
    tail.next = (list1 != null) ? list1 : list2;
    return dummyHead.next;
}

ListNode getMid(ListNode head) {
    ListNode midPrev = null;
    while (head != null && head.next != null) {
        midPrev = (midPrev == null) ? head : midPrev.next;
        head = head.next.next;
    }
    ListNode mid = midPrev.next;
    midPrev.next = null;
    return mid;
}

}

So in the sortList method on the line

 ListNode left = sortList(head);

how does this assignment work? Head is not incremented so on each recursive call wouldnt it just call the method over and over again on the same value?

I've walked through this by hand and heres where i get stuck.

5 -> 3 -> 4
SortList(5)
head = 5 
mid = getMid(5) == 3
        getMid(5)
            mid prev = null    -> 5
            head = 5           -> 4
            mid = 3 
            return 3 
left = sortList(5)
      mid = getMid(5) = 3
      left = sortList(5)
            mid = sortList(5) = 3
            left = sortList(5)

As you can see theres always a call to sortList(5) for every assignment to left. I'm pretty decent and leetcode but this question is really stumping me. All help is much appreciated!

Answer 1

It works because getMid(head) splits the list into two sublists.

After the first call to getMid() you have the two sublists:

head: 5
mid:  3 -> 4

Calling sortList(head) on the first sublist returns immediately (because head.next is null)

Calling sortList(mid) with the second sublist splits that list into two further sublists:

head': 3
mid': 4

Calling sortList on both sublists also returns immediately (because in both sublists head.next is null).

The code then proceeds to merge head' and mid' which results in 3 -> 4.

After that the list head and the result of the previous merge (3 -> 4) are merged together, which gives the final result:

3 -> 4 -> 5

---

I try to explain in a bit more detail with some pictures.

This is the list on the first call to sortList(head):

        ListNode    ListNode    ListNode
head -> next     -> next     -> next     -> null
        val: 5      val: 3      val: 4

getMid(head) changes the list and returns a reference to the middle element:

        ListNode
head -> next     -> null
        val: 5

        ListNode    ListNode
mid  -> next     -> next     -> null
        val: 3      val: 4

That is, although the reference head itself did not change, the list it references changed because head.next changed!

What happens if we call sortList(head) with this reduced list?

The first statement in sortList(head) is

if (head == null || head.next == null)
    return head;

Calling sortList(head) (second level) with the reduced list

        ListNode
head -> next     -> null
        val: 5

has head.next == null, so it returns immediately the value of head and in the caller results in left being set to the value of head.

The next line in the first level of the sortList() call is ListNode right = sortList(mid);.

Calling sortList(head) (second level) with the split of list

        ListNode    ListNode
mid  -> next     -> next     -> null
        val: 3      val: 4

What was mid in the first level is now called head (I call it head' to distinguish it from the head in the first level)

         ListNode    ListNode
head' -> next     -> next     -> null
         val: 3      val: 4

getMid(head) again changes the list and returns a reference to the middle element:

         ListNode
head' -> next     -> null
         val: 3

         ListNode
mid'  -> next     -> null
         val: 4