Sort List (Merge Sort on LL)

▶

Steps

setup

Initialize and Calculate Length

Start with the input list [4, 2, 1, 3]. We traverse the list to count its length, which is 4.

💡 Knowing the length is essential to control the size of sublists we merge in each pass.

Line:

length = 0
node = head
while node:
    length += 1
    node = node.next

💡 The list length determines how many merge passes are needed.

setup

Create Dummy Node and Initialize Size

Create a dummy node pointing to head to simplify merges. Initialize sublist size to 1 for the first merge pass.

💡 Dummy node helps easily connect merged lists without special cases for head changes.

Line:

dummy = ListNode(0, head)
size = 1

💡 Starting with size 1 means we merge pairs of single nodes first.

fill_row

Start First Merge Pass with size=1: Set cur and tail

Set 'cur' to the first real node (dummy.next) and 'tail' to dummy. We'll merge pairs of size 1 sublists.

💡 Pointers 'cur' and 'tail' help track where we are splitting and merging in the list.

Line:

cur = dummy.next
tail = dummy

💡 We prepare to split and merge sublists starting from the head.

split

Split left sublist of size 1

Split the list starting at 'cur' into a left sublist of size 1. The left sublist is node with value 4.

💡 Splitting isolates sublists to merge independently.

Line:

left = cur
right = split(left, size)

💡 Splitting at size 1 means left is a single node.

split

Split right sublist of size 1

Split the list starting at 'right' into a right sublist of size 1. The right sublist is node with value 2.

💡 Right sublist is also isolated for merging with left.

Line:

cur = split(right, size)

💡 Splitting right sublist isolates the next pair for merging.

merge

Merge left and right sublists (4 and 2)

Merge the two sublists [4] and [2]. Since 2 < 4, 2 becomes the new head of merged sublist.

💡 Merging combines two sorted sublists into one sorted list.

Line:

merged = merge(left, right)
tail.next = merged

💡 Merge compares node values to build sorted sublist.

traverse

Advance tail pointer after merge

Move 'tail' pointer to the end of the merged sublist (node with value 4) to prepare for next merge.

💡 Tail tracks the end of the sorted list built so far.

Line:

while tail.next:
    tail = tail.next

💡 Advancing tail ensures new merges attach correctly.

split

Split next left sublist of size 1 (node 1)

Split the next sublist starting at 'cur' into left sublist of size 1, node with value 1.

💡 We continue splitting the list into pairs to merge.

Line:

left = cur
right = split(left, size)

💡 Splitting isolates the next pair for merging.

split

Split next right sublist of size 1 (node 3)

Split the next sublist starting at 'right' into right sublist of size 1, node with value 3.

💡 Right sublist isolated for merging with left.

Line:

cur = split(right, size)

💡 Splitting right sublist isolates next pair for merging.

merge

Merge left and right sublists (1 and 3)

Merge the two sublists [1] and [3]. Since 1 < 3, 1 becomes the new head of merged sublist.

💡 Merging combines two sorted sublists into one sorted list.

Line:

merged = merge(left, right)
tail.next = merged

💡 Merge compares node values to build sorted sublist.

traverse

Advance tail pointer after second merge

Move 'tail' pointer to the end of the merged sublist (node with value 3) to prepare for next merge.

💡 Tail tracks the end of the sorted list built so far.

Line:

while tail.next:
    tail = tail.next

💡 Advancing tail ensures new merges attach correctly.

expand

Double sublist size to 2 for next merge pass

Increase the sublist size to 2 to merge pairs of size 2 sublists next.

💡 Doubling size merges larger sorted sublists each pass.

Line:

size <<= 1

💡 Doubling size reduces number of passes needed to sort entire list.

fill_row

Start second merge pass with size=2: Set cur and tail

Set 'cur' to dummy.next and 'tail' to dummy to start merging pairs of size 2 sublists.

💡 We will merge [2,4] and [1,3] sublists now.

Line:

cur = dummy.next
tail = dummy

💡 Pointers reset to start new merge pass.

split

Split left sublist of size 2 ([2,4])

Split the list starting at 'cur' into left sublist of size 2: nodes with values 2 and 4.

💡 Splitting isolates the first half of the pair to merge.

Line:

left = cur
right = split(left, size)

💡 Left sublist is now two nodes long.

split

Split right sublist of size 2 ([1,3])

Split the list starting at 'right' into right sublist of size 2: nodes with values 1 and 3.

💡 Right sublist isolated for merging with left.

Line:

cur = split(right, size)

💡 Right sublist is now two nodes long.

merge

Merge left and right sublists ([2,4] and [1,3])

Merge the two sorted sublists [2,4] and [1,3]. Compare nodes and build sorted merged list [1,2,3,4].

💡 Merging larger sublists combines sorted sequences into bigger sorted sequences.

Line:

merged = merge(left, right)
tail.next = merged

💡 Merge compares nodes stepwise to maintain sorted order.

traverse

Advance tail pointer after final merge

Move 'tail' pointer to the end of the merged list (node with value 4).

💡 Tail points to the last node of the sorted list.

Line:

while tail.next:
    tail = tail.next

💡 Tail marks the end for any further merges (none left here).

expand

Double size to 4, which equals list length; end merging

Double sublist size to 4, which is equal to list length, so sorting is complete.

💡 When size >= length, the entire list is sorted.

Line:

size <<= 1

💡 Doubling size beyond length ends the merge passes.

reconstruct

Return sorted list starting at dummy.next

Return the sorted list starting at dummy.next, which is node with value 1.

💡 The dummy node's next pointer now points to the fully sorted list.

Line:

return dummy.next

💡 Sorted list head is returned for use.

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

def merge(l1, l2):
    dummy = ListNode(0)  # STEP 6,10,16
    tail = dummy
    while l1 and l2:
        if l1.val < l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next
    tail.next = l1 or l2
    return dummy.next

def split(head, size):
    for i in range(size - 1):  # STEP 4,5,8,9,14,15
        if head:
            head = head.next
        else:
            break
    if not head:
        return None
    second = head.next
    head.next = None
    return second

def sortList(head):
    if not head or not head.next:
        return head
    length = 0
    node = head
    while node:  # STEP 1
        length += 1
        node = node.next
    dummy = ListNode(0, head)  # STEP 2
    size = 1
    while size < length:  # STEP 12,18
        cur = dummy.next  # STEP 3,13
        tail = dummy
        while cur:
            left = cur
            right = split(left, size)  # STEP 4,5,8,9,14,15
            cur = split(right, size)
            merged = merge(left, right)  # STEP 6,10,16
            tail.next = merged
            while tail.next:
                tail = tail.next  # STEP 7,11,17
        size <<= 1
    return dummy.next  # STEP 19

📊

Sort List (Merge Sort on LL) - Watch the Algorithm Execute, Step by Step

Watching each pointer move and merge operation helps you understand how merge sort works on linked lists without extra space.

traverse

4

→

2

→

1

→

3

Result: 4

setup

0

→

4

→

2

→

1

→

3

setup

0

→

4

→

2

→

1

→

3

split

0

→

4

→

2

→

1

→

3

split

0

→

4

→

2

→

1

→

3

merge

0

→

4

→

2

→

1

→

3

traverse

0

→

4

→

2

→

1

→

3

split

0

→

4

→

2

→

1

→

3

split

0

→

4

→

2

→

1

→

3

merge

0

→

4

→

2

→

1

→

3

traverse

0

→

4

→

2

→

1

→

3

expand

0

→

4

→

2

→

1

→

3

setup

0

→

4

→

2

→

1

→

3

split

0

→

4

→

2

→

1

→

3

split

0

→

4

→

2

→

1

→

3

merge

0

→

4

→

2

→

1

→

3

traverse

0

→

4

→

2

→

1

→

3

expand

0

→

4

→

2

→

1

→

3

reconstruct

1

→

2

→

3

→

4

Result: [1, 2, 3, 4]

Key Takeaways

✓ Merge sort on linked lists works by splitting the list into smaller sublists and merging them in sorted order.

This is hard to see from code alone because the pointer manipulations and sublist boundaries are implicit.

✓ Using a dummy node simplifies merging by providing a stable anchor point for the sorted list.

Without visualization, it's not obvious how dummy helps avoid special cases for head changes.

✓ Doubling the sublist size each pass reduces the number of merges and leads to a fully sorted list efficiently.

The iterative size doubling is a key optimization that is clearer when watching the passes visually.

Practice

1. The following code attempts to merge k sorted linked lists using a min-heap. Identify the line that contains a subtle bug that can cause incorrect merging or runtime errors.

medium

A. Line: current.next = smallest

B. Line: Missing 'current = current.next' after attaching smallest

C. Line: while heap:

D. Line: if node: heapq.heappush(heap, node)

Solution

1. Step 1: Review pointer updates in loop

   After attaching smallest to current.next, current must move forward.

2. Step 2: Identify missing line

   Code lacks 'current = current.next', so current stays, causing incorrect list linking.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Without advancing current, merged list nodes overwrite each other [OK]

Hint: Always advance current pointer after attaching a node [OK]

Common Mistakes:

• Forgetting to move current pointer
• Misplacing heap push conditions
• Confusing heap pop with list traversal

2. Examine the following buggy code snippet for checking if a linked list is a palindrome using the recursive two-pointer technique. Which line contains the subtle bug that causes incorrect results on empty or single-node lists?

medium

A. Line: if not self._recursively_check(current.next):

B. Line: if current.next is not None:

C. Line: if self.front.val != current.val:

D. Line: self.front = self.front.next

Solution

1. Step 1: Analyze base case condition

   The original buggy code used if current.next is not None: which fails when current is None (empty list) causing AttributeError.

2. Step 2: Correct base case check

   The correct check should be if current is not None: to handle empty and single-node lists safely.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Incorrect base case leads to exceptions or wrong results on edge cases [OK]

Hint: Base case must check current, not current.next [OK]

Common Mistakes:

• Using current.next in base case
• Forgetting to handle empty list
• Moving front pointer too early

3. Consider the following buggy code snippet for removing the nth node from the end of a linked list. Which line contains the subtle bug that causes incorrect behavior when removing the head node?

medium

A. Line 13: Wrong condition for node removal

B. Line 10: Incorrect base case for recursion

C. Line 5: Missing dummy node initialization

D. Line 15: Returning head instead of dummy.next

Solution

1. Step 1: Identify missing dummy node

   Without a dummy node, removing the head node causes pointer errors or incorrect list head.

2. Step 2: Check recursion call and return

   Recursion is called on head, but no dummy means no safe predecessor to update head pointer.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Dummy node is essential to handle head removal safely [OK]

Hint: Always use dummy node to handle head removal [OK]

Common Mistakes:

• Not using dummy node
• Incorrect recursion base case
• Returning wrong node after removal

4. What is the time complexity of the optimal iterative approach that reverses nodes in k-groups in a singly linked list of length n? Assume k is a fixed positive integer.

medium

A. O(n log k)

B. O(n * k)

C. O(n / k * k^2)

D. O(n)

Solution

1. Step 1: Identify the number of groups processed

   The list of length n is divided into approximately n/k groups.

2. Step 2: Analyze reversal cost per group

   Each group reversal takes O(k) time, so total time is (n/k) * k = O(n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Each node is visited and reversed exactly once [OK]

Hint: Reversing fixed-size groups leads to linear time [OK]

Common Mistakes:

• Mistaking O(n * k) by multiplying n and k without division
• Confusing group count and reversal cost per group

5. The following code attempts to rotate a linked list to the right by k places. Identify the line that contains a subtle bug that can cause the list to become cyclic or truncated incorrectly.

medium

A. Line: tail.next = head # make circular

B. Line: slow.next = slow # BUG: incorrect break causing cycle

C. Line: for _ in range(k): fast = fast.next

D. Line: k = k % length

Solution

1. Step 1: Understand the purpose of breaking the list

   After rotation, the list must be broken at the new tail by setting slow.next = None.

2. Step 2: Identify the bug

   The original code sets slow.next = slow, which creates a cycle instead of breaking the list.

3. Step 3: Correct fix

   Change to slow.next = None to properly break the list.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Correct break is slow.next = None [OK]

Hint: Break list by setting slow.next = None [OK]

Common Mistakes:

• Setting slow.next to itself or wrong node causing cycles
• Not handling k modulo length correctly
• Forgetting to make list circular before rotation