DSA sheet · Linked List · Merge / Sort pattern

Sort List

Now the list is not sorted, and we must sort it. The teacher's answer is merge sort on a linked list, and she points out that it needs two patterns from this sheet at once: fast/slow pointers to find the middle (the "divide" step) and merging two sorted lists (the "conquer" step, the previous video, which is the prerequisite here). Before that, she shows the brute force: copy the values to an array, sort, and write them back.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Linked lists from scratch, fast/slow, merging, recursion
• Part A · Brute force: copy, sort, overwrite
• Part B · Optimal: merge sort on the list
• Part C · Revision page

Part 0 · Before starting

Nodes, head, None

A linked list is a chain of nodes; each node has a val and a next link. The last node's next is None. The head is the first node; an empty list has head = None.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

  [4] → [2] → [1] → [3] → None
   ↑
  head

Walking, and why there's no index

We walk with curr = curr.next. There's no list[i]: to reach position i we must walk i steps from the head, which costs O(n). This matters a lot here: merge sort on an array finds the middle with mid = (lo + hi) // 2 in one step. A linked list can't do that, so we need another way to find the middle.

Save next before you change a pointer

If you overwrite node.next without keeping the old value, the rest of the chain is lost. In the split step below we save second = slow.next before setting slow.next = None.

Tool 1: fast and slow pointers find the middle

Two pointers start near the head. slow moves 1 node per step; fast moves 2. When fast reaches the end, slow has covered half the distance, so it stands in the middle. For this problem the teacher starts slow = head and fast = head.next, and loops while fast and fast.next. With that start, slow stops on the last node of the left half:

  even (4 nodes):   [4] → [2] → [1] → [3] → None
  start              s     f
  after 1 step             s           f        fast.next is None → stop
                    left = 4,2      right = 1,3   (slow on 2, end of left half)

  odd (5 nodes):    [5] → [4] → [3] → [2] → [1] → None
  start              s     f
  after 1 step             s           f
  after 2 steps                  s                 f = None → stop
                    left = 5,4,3      right = 2,1

Even length: the two halves are equal. Odd length: the left half gets the extra node. Either way both halves are non-empty when the list has 2 or more nodes, which is what makes the recursion end (see Doubt 2 in Part B).

Tool 2: merging two sorted lists with a dummy and a tail

From Problem 18: make a fake dummy node, keep a tail pointer (current) on the last placed node, repeatedly attach the smaller of the two front nodes, move that list and the tail, then attach whatever is left. Return dummy.next. The dummy removes the special case of "which node becomes the first one". It runs in O(n + m) and creates no new nodes.

Tool 3: recursion on lists

A recursive function calls itself on a smaller input. Here: "to sort a list, sort its left half, sort its right half (both by calling ourselves), then merge them". The base case, where we stop calling, is a list with 0 or 1 node: it's already sorted. Every call waiting for its children sits on Python's call stack.

Merge sort in one line: divide and conquer

Divide: split into two halves, again and again, until every piece has 1 node. Conquer: a 1-node list is sorted on its own, so merge pieces back in pairs, each merge producing a bigger sorted piece, until one sorted list remains.

Part A · Brute force: copy, sort, overwrite

LeetCode 148

1The question in simple words

You get the head of a linked list in any order. Sort it in ascending order and return the head of the sorted list.

  input:  [4] → [2] → [1] → [3] → None
  output: [1] → [2] → [3] → [4] → None

2What the constraints tell us

• Number of nodes: 0 to 5 × 10⁴. 0 is allowed → base case: an empty list returns None.
• Why check the size? The rough rule from the teacher's complexity video: beyond about 10⁸ operations you risk TLE, and at 10⁹ you'll surely get it. With n = 5 × 10⁴, n log n is about 10⁶, which is fine; O(n²) would be about 2.5 × 10⁹, too slow. So we want an n log n sort, and merge sort is the best fit.
• Values: −10⁵ to 10⁵, positive or negative, well inside a normal integer range (she compares it with the ~10⁹ int limit), so no overflow worry.

3Intuition

If this were a Python list like [4, 2, 1, 3], we'd just call .sort(). So: copy the values into a Python list, sort it, then either build a new linked list, or (better) overwrite the values in the original nodes in the new order.

4Building the logic

1. Walk the list: values = [4, 2, 1, 3].
2. Sort: [1, 2, 3, 4].
3. Walk the list again with an index i starting at 0, writing values[i] into each node: the nodes now read 1, 2, 3, 4. The links never change; only the numbers in the boxes do.

5Approach steps

1. If head is None → return None.
2. Copy all values into an array.
3. Sort the array.
4. Walk the list from head again and overwrite each node's value in order. Return head.

6Code (Python)

class Solution:
    def sortList(self, head):
        if head is None:
            return None

        values = []
        curr = head
        while curr is not None:        # copy values out
            values.append(curr.val)
            curr = curr.next

        values.sort()                  # n log n built-in sort

        curr = head
        i = 0
        while curr is not None:        # write them back in order
            curr.val = values[i]
            i += 1
            curr = curr.next
        return head

7Code line by line

8Dry run

9Complexity & remember

• Time: O(n) to copy + O(n log n) to sort + O(n) to write back → O(n log n). It's accepted, but slow on LeetCode.
• Space: O(n) for the array. That's the part we want to improve, and the interviewer wants to see the merge logic, not a library call.

Part B · Optimal: merge sort on the list

1The question in simple words

Same question: sort the list. Now we move nodes (rewire next links) instead of copying values out, using merge sort.

2What the constraints tell us

• n up to 5 × 10⁴ → we need O(n log n). Merge sort gives that always (no bad worst case, unlike quick sort).
• 0 or 1 node must work → that becomes our base case.

3Intuition: which patterns do we need?

The teacher goes through the linked list patterns covered so far and asks which ones help:

Merge sort on an array: cut at mid, sort each half, merge. On a list: fast/slow replaces mid, and merge-two-sorted-lists replaces the array merge.

4Building the logic from the example 4 → 2 → 1 → 3

Divide: find the split point

slow on 4, fast on 2 (head.next). fast.next exists → slow moves to 2, fast jumps to 3. Now fast.next is None → stop. slow is on 2.

• The left half starts at head (4).
• The right half starts at slow.next (1). Save it: second = slow.next.
• Cut the chain: slow.next = None. Now we have two separate lists, 4 → 2 and 1 → 3.

  before:  [4] → [2] → [1] → [3] → None
                  slow   ↑
                       second

  after slow.next = None:
           [4] → [2] → None        [1] → [3] → None
           head                    second

Repeat on each half. For 4 → 2: slow on 4, fast on 2; fast.next is None, so the loop doesn't run at all. Left = 4, right = slow.next = 2, cut. Same for 1 → 3. We stop dividing when a piece has one node: its head.next is None.

Conquer: merge back

A single node is sorted on its own. So [4] and [2] are two sorted lists → merge them → 2 → 4. Likewise [1] and [3] → 1 → 3. Then merge 2 → 4 with 1 → 3 → 1 → 2 → 3 → 4. Each merge is the Problem 18 code: dummy, current, take the smaller front, attach the leftover.

5Approach steps

1. If the list has 0 or 1 node → return head.
2. slow = head, fast = head.next; while fast and fast.next: slow one step, fast two steps.
3. second = slow.next; slow.next = None (split).
4. left = sortList(head), right = sortList(second).
5. Return merge(left, right).

6Code (Python)

class Solution:
    def sortList(self, head):
        if head is None or head.next is None:    # 0 or 1 node: sorted
            return head

        # divide: find the end of the left half
        slow = head
        fast = head.next
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next

        second = slow.next      # head of the right half (save it first)
        slow.next = None        # cut the list in two

        left = self.sortList(head)       # sort the left half
        right = self.sortList(second)    # sort the right half
        return self.merge(left, right)   # conquer

    def merge(self, l1, l2):             # Problem 18
        dummy = ListNode(0)
        current = dummy
        while l1 is not None and l2 is not None:
            if l1.val <= l2.val:
                current.next = l1
                l1 = l1.next
            else:
                current.next = l2
                l2 = l2.next
            current = current.next
        if l1 is not None:
            current.next = l1
        if l2 is not None:
            current.next = l2
        return dummy.next

7Code line by line

8Dry run: 4 → 2 → 1 → 3

The split-and-merge recursion tree. Going down = dividing (fast/slow + cut). Coming up = merging. Each box shows the list a call receives → what it returns.

                         sortList(4→2→1→3)
                    slow stops on 2 · cut after 2
                    returns merge(2→4, 1→3) = 1→2→3→4
                     /                           \
          sortList(4→2)                         sortList(1→3)
      slow stays on 4 · cut after 4         slow stays on 1 · cut after 1
      returns merge(4, 2) = 2→4             returns merge(1, 3) = 1→3
          /           \                         /           \
   sortList(4)    sortList(2)            sortList(1)    sortList(3)
   base case      base case              base case      base case
   returns 4      returns 2              returns 1      returns 3

   DIVIDE ↓   level 0: [4 2 1 3]
              level 1: [4 2]   [1 3]
              level 2: [4] [2] [1] [3]      ← log₂4 = 2 levels of splitting
   MERGE  ↑   level 1: [2 4]   [1 3]
              level 0: [1 2 3 4]

The story, call by call:

1. S(4→2→1→3): not a base case. slow = 4, fast = 2 → one step → slow = 2, fast = 3; fast.next is None, stop. second = 1. Cut 2.next = None. Call S(4→2). S(4213) waits.
2. S(4→2): slow = 4, fast = 2; fast.next is None, the loop doesn't run. second = 2. Cut 4.next = None. Call S(4).
3. S(4): 4.next is None → base case → returns 4.
4. Back in S(4→2): call S(2) → base case → returns 2.
5. S(4→2) merges [4] and [2]: 4 ≤ 2? No → take 2; then l2 is None → attach 4. Returns 2 → 4.
6. Back in S(4→2→1→3): call S(1→3): slow = 1, fast = 3, no loop. second = 3, cut 1.next = None. S(1) returns 1, S(3) returns 3. Merge → 1 → 3.
7. S(4→2→1→3) merges 2 → 4 with 1 → 3 (table below). Returns 1 → 2 → 3 → 4. The call stack is empty. ✓

The newest call is on top (red). The stack is never deeper than the number of split levels + 1, which is about log n.

The final merge, l1 = 2 → 4, l2 = 1 → 3:

  just after the top-level cut:
     [4] → [2] → None          [1] → [3] → None

  after the level-1 merges:
     [2] → [4] → None          [1] → [3] → None

  after the final merge:
     [1] → [2] → [3] → [4] → None   (the same 4 nodes, relinked)

9Complexity & remember

• Time O(n log n). The list is halved at each level, so there are about log₂ n levels (for 4 nodes: log₂ 4 = 2 levels of splitting, as in the tree). On every level, the merges together touch all n nodes once → O(n) per level. The fast/slow walks on a level also cost O(n) in total. So n work × log n levels = n log n.
• Space O(log n): no array, no new nodes (just one dummy per merge), but the recursion keeps up to about log n calls waiting on the call stack.
• Same O(n log n) time as the brute force, but no O(n) array and it actually shows the merge logic, which is why it's the expected answer.

Part C · Revision page

class ListNode:
    def __init__(self, val=0, next=None):
        self.val, self.next = val, next

def build(vals):
    dummy = tail = ListNode()
    for v in vals:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

s = Solution()
print(to_list(s.sortList(build([4, 2, 1, 3]))))         # [1, 2, 3, 4]
print(to_list(s.sortList(build([-1, 5, 3, 4, 0]))))     # [-1, 0, 3, 4, 5]
print(to_list(s.sortList(build([]))))                   # []
print(to_list(s.sortList(build([7]))))                  # [7]

Based on this video: Sort List