Algorithm-Day34-Sort-List-lc-148

🧩 Problem Description

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

You must sort in O(n log n) time and use constant space complexity (no array conversion).

---

💬 Example

Input: head = [4,2,1,3]
Output: [1,2,3,4]

💡 Intuition

We cannot use extra space like arrays. So we apply merge sort on the linked list itself:

• Split the list into halves using the slow/fast pointer technique
• Recursively sort each half
• Merge the two sorted halves (like in lc-21)

This gives us O(n log n) time and uses O(1) extra space for list nodes.

---

🔢 Java Code (Top-Down Merge Sort)

class Solution {
    public ListNode sortList(ListNode head) {
        // Base case
        if (head == null || head.next == null) return head;

        // Step 1: Split list into halves
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode mid = slow.next;
        slow.next = null;

        // Step 2: Recursively sort each half
        ListNode left = sortList(head);
        ListNode right = sortList(mid);

        // Step 3: Merge sorted halves
        return merge(left, right);
    }

    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0), curr = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }

        curr.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}

---

⏱ Time and Space Complexity

• Time Complexity: O(n log n)
• Space Complexity: O(log n) due to recursion stack (not extra list memory)

---

✍️ Summary

• Use top-down merge sort directly on the list.
• Core techniques:
  • Fast/slow pointer to find middle
  • Recursive divide-and-conquer
  • Merging two sorted linked lists
• Efficient, in-place sorting without using arrays

Make sure you’ve mastered lc-21 (merge two sorted lists) before this one — it’s the foundation of merging steps here.