Leetcode - 148. Sort List

Sorting a linked list isn’t as straightforward as sorting an array. With arrays, we can do quick sort or heap sort thanks to random access. But linked lists only allow sequential access, making those methods inefficient.

That’s where merge sort shines. It works beautifully on linked lists because splitting and merging can be done in-place with pointers. Let’s dive in.

---

🔹 Problem Statement

Given the head of a linked list, return the list sorted in ascending order.

Example:

Input:  4 → 2 → 1 → 3
Output: 1 → 2 → 3 → 4

---

🔹 Approach: Divide and Conquer

We apply the merge sort strategy:

1. Divide: Use the slow–fast pointer trick to find the middle and split the list into two halves.
2. Conquer: Recursively sort both halves.
3. Combine: Merge the two sorted halves back together.

---

🔹 Step 1: Find the Middle

We use two pointers:

• slow moves one step at a time.
• fast moves two steps at a time.

When fast reaches the end, slow will be at the middle.

const getMid = (head) => {
    let slow = head;
    let fast = head.next; // ensures we stop at the "first middle" for even length

    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }

    return slow; // returns middle node
}

---

🔹 Step 2: Merge Two Sorted Lists

This step is similar to merging two sorted arrays:

const merge = (list1, list2) => {
    let dummy = new ListNode(0);
    let tail = dummy;

    while (list1 && list2) {
        if (list1.val < list2.val) {
            tail.next = list1;
            list1 = list1.next;
        } else {
            tail.next = list2;
            list2 = list2.next;
        }
        tail = tail.next;
    }

    // attach the remaining part
    tail.next = list1 || list2;
    return dummy.next;
}

---

🔹 Step 3: Recursive Merge Sort

var sortList = function (head) {
    if (!head || !head.next) return head; // base case

    // 1. Split into two halves
    let mid = getMid(head);
    let right = mid.next;
    mid.next = null; // break the link
    let left = head;

    // 2. Recursively sort both halves
    left = sortList(left);
    right = sortList(right);

    // 3. Merge the sorted halves
    return merge(left, right);
};

---

🔹 Walkthrough Example: 4 → 2 → 1 → 3

Step 1: Initial Split

• Mid = 2
• Left = 4 → 2
• Right = 1 → 3

---

Step 2: Sort Left (4 → 2)

• Mid = 4
• Left = 4
• Right = 2
• Merge → 2 → 4

---

Step 3: Sort Right (1 → 3)

• Mid = 1
• Left = 1
• Right = 3
• Merge → 1 → 3

---

Step 4: Merge the Halves

Merge 2 → 4 and 1 → 3:

• Compare 2 vs 1 → pick 1
• Compare 2 vs 3 → pick 2
• Compare 4 vs 3 → pick 3
• Leftover → 4

Result: 1 → 2 → 3 → 4 ✅

---

Recursion Tree

sort(4 2 1 3)
   /        \
sort(4 2)  sort(1 3)
  /   \      /   \
 4     2    1     3

Merges:
(4,2) → (2 4)
(1,3) → (1 3)
(2 4) + (1 3) → (1 2 3 4)

---

🔹 Complexity Analysis

• Time Complexity:

  • Splitting takes O(log n) levels.
  • Each merge across levels costs O(n).
  • Overall: O(n log n).

• Space Complexity:

  • Merge happens in-place with pointers → O(1) extra space.
  • Recursion depth = O(log n).

---

🔹 Why Merge Sort Works Best for Linked Lists?

• Quick sort needs random access (bad for linked lists).
• Merge sort only needs sequential traversal (perfect fit).
• Splitting and merging are pointer operations, so memory overhead is minimal.

---

✅ Final Takeaway

• Use slow–fast pointers to find the middle.
• Recursively sort both halves.
• Merge with pointer juggling.
• Achieve O(n log n) efficiency with minimal space overhead.

👉 Next time someone asks “How do you sort a linked list?”, you’ve got a clean, interview-ready answer. 🚀

---