Sort a Linked List Using Merge Sort in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Merge Sort on a Linked List

What is the printed state of the linked list after applying merge sort on the list 4 -> 2 -> 1 -> 3 -> null?

DSA Python

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

def print_list(head):
    curr = head
    result = []
    while curr:
        result.append(str(curr.val))
        curr = curr.next
    print(' -> '.join(result) + ' -> null')

def merge_sort(head):
    if not head or not head.next:
        return head

    # Find middle
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    mid = slow.next
    slow.next = None

    left = merge_sort(head)
    right = merge_sort(mid)

    return merge(left, right)

def merge(l1, l2):
    dummy = Node(0)
    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

# Create linked list 4 -> 2 -> 1 -> 3 -> null
head = Node(4)
head.next = Node(2)
head.next.next = Node(1)
head.next.next.next = Node(3)

sorted_head = merge_sort(head)
print_list(sorted_head)

A 4 -> 3 -> 2 -> 1 -> null

B 1 -> 2 -> 3 -> 4 -> null

C 1 -> 3 -> 2 -> 4 -> null

D 2 -> 1 -> 3 -> 4 -> null

💡 Hint

Remember that merge sort splits the list and merges sorted halves.

Merge sort splits the list into halves recursively and merges them in sorted order. The final sorted list is 1 -> 2 -> 3 -> 4 -> null.

❓ Predict Output

intermediate

Resulting List After One Merge Step

Given two sorted linked lists: 1 -> 4 -> null and 2 -> 3 -> null, what is the merged list after one merge step?

DSA Python

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

def print_list(head):
    curr = head
    result = []
    while curr:
        result.append(str(curr.val))
        curr = curr.next
    print(' -> '.join(result) + ' -> null')

def merge(l1, l2):
    dummy = Node(0)
    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

# Create lists
l1 = Node(1)
l1.next = Node(4)
l2 = Node(2)
l2.next = Node(3)

merged_head = merge(l1, l2)
print_list(merged_head)

A 1 -> 2 -> 3 -> 4 -> null

B 1 -> 4 -> 2 -> 3 -> null

C 2 -> 3 -> 1 -> 4 -> null

D 4 -> 3 -> 2 -> 1 -> null

💡 Hint

Merging two sorted lists results in a sorted combined list.

The merge function combines two sorted lists into one sorted list. The merged list is 1 -> 2 -> 3 -> 4 -> null.

🔧 Debug

advanced

Identify the Bug in Merge Sort Implementation

What error will this merge sort code on linked list produce when run?

DSA Python

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

def merge_sort(head):
    if not head or not head.next:
        return head

    slow, fast = head, head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next

    mid = slow.next
    slow.next = None

    left = merge_sort(head)
    right = merge_sort(mid)

    return merge(left, right)

def merge(l1, l2):
    dummy = Node(0)
    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

head = Node(3)
head.next = Node(1)
head.next.next = Node(2)

sorted_head = merge_sort(head)

A RecursionError: maximum recursion depth exceeded

B TypeError: unsupported operand type(s) for <

C No error, sorts correctly

D AttributeError: 'NoneType' object has no attribute 'next'

💡 Hint

Check the initialization of fast pointer and the while loop condition.

The fast pointer is initialized to head, but the loop condition checks fast.next and fast.next.next. When the list is short, fast.next.next can be None, causing AttributeError.

📝 Syntax

advanced

Syntax Error in Merge Function

Which option contains a syntax error in the merge function for linked lists?

DSA Python

def merge(l1, l2):
    dummy = Node(0)
    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

A Missing colon after if condition

B Missing colon after else

C Indentation error on tail = tail.next

D Missing return statement

💡 Hint

Check the if statement syntax carefully.

The if statement is missing a colon at the end of the condition line, causing a syntax error.

🚀 Application

expert

Number of Recursive Calls in Merge Sort

For a linked list of length 8, how many total calls to merge_sort are made during the full sort process?

A 7

B 8

C 15

D 16

💡 Hint

Each call splits the list into two halves until single nodes remain.

Merge sort on a list of length n makes 2n-1 calls: each node is a base call plus all internal calls. For n=8, total calls = 15.

Practice

1. What is the main advantage of using merge sort to sort a linked list compared to quicksort?

easy

A. Quicksort is unstable, but merge sort is always unstable.

B. Merge sort uses less memory than quicksort for linked lists.

C. Merge sort does not require random access, which suits linked lists well.

D. Merge sort sorts linked lists in-place without extra space.

Solution

1. Step 1: Understand linked list access

   Linked lists do not support fast random access, unlike arrays.

2. Step 2: Compare sorting algorithms

   Merge sort works by splitting and merging, which only needs sequential access, making it suitable for linked lists.

3. Final Answer:

   Merge sort does not require random access, which suits linked lists well. -> Option C

4. Quick Check:

   Linked list + merge sort = no random access needed [OK]

Hint: Merge sort fits linked lists because it uses sequential access [OK]

Common Mistakes:

• Thinking quicksort is better for linked lists
• Believing merge sort sorts in-place without extra space
• Confusing stability properties of sorting algorithms

2. Which of the following is the correct base case condition in a recursive merge sort function for a linked list?

easy

A. if head is None and head.next is None: return None

B. if head is None or head.next is None: return None

C. if head.next is None: return None

D. if head is None or head.next is None: return head

Solution

1. Step 1: Identify base case for recursion

   When the list is empty or has one node, it is already sorted.

2. Step 2: Correct base case condition

   Check if head is None (empty list) or head.next is None (single node), then return head.

3. Final Answer:

   if head is None or head.next is None: return head -> Option D

4. Quick Check:

   Base case returns head when list size ≤ 1 [OK]

Hint: Base case returns head if list empty or single node [OK]

Common Mistakes:

• Returning None instead of head for single node
• Using 'and' instead of 'or' in condition
• Missing base case leading to infinite recursion

3. What will be the output linked list after applying merge sort on the following linked list?

4 -> 2 -> 1 -> 3 -> None

medium

A. 1 -> 2 -> 3 -> 4 -> None

B. 4 -> 3 -> 2 -> 1 -> None

C. 2 -> 1 -> 3 -> 4 -> None

D. 1 -> 3 -> 2 -> 4 -> None

Solution

1. Step 1: Split the list into halves

   Split into (4 -> 2) and (1 -> 3).

2. Step 2: Recursively sort and merge

   Sort (4 -> 2) to (2 -> 4), sort (1 -> 3) to (1 -> 3), then merge to (1 -> 2 -> 3 -> 4).

3. Final Answer:

   1 -> 2 -> 3 -> 4 -> None -> Option A

4. Quick Check:

   Sorted ascending order = 1 -> 2 -> 3 -> 4 [OK]

Hint: Merge sort outputs sorted list in ascending order [OK]

Common Mistakes:

• Confusing merge order and producing unsorted output
• Not splitting list correctly
• Merging without sorting halves first

4. Given this merge function snippet for linked lists, what is the bug?

def merge(left, right):
    if not left:
        return right
    if not right:
        return left
    if left.val < right.val:
        result = left
        result.next = merge(left.next, right)
    else:
        result = right
        result.next = merge(left, right.next)
    return result

medium

A. The comparison should be <= instead of < to maintain stability.

B. No bug; function correctly merges two sorted lists.

C. The function does not handle empty lists properly.

D. The function should return None at the end instead of result.

Solution

1. Step 1: Analyze base cases

   Returns right if left is None, and left if right is None, correctly handling empty lists.

2. Step 2: Check recursive merge logic

   Compares values, assigns result, and recursively merges remaining nodes correctly.

3. Final Answer:

   No bug; function correctly merges two sorted lists. -> Option B

4. Quick Check:

   Merge function logic is correct and complete [OK]

Hint: Check base cases and recursion carefully for merge correctness [OK]

Common Mistakes:

• Thinking <= is required for stability (not always needed)
• Missing base case returns
• Returning None instead of merged list

5. You have a linked list with nodes:

5 -> 3 -> 8 -> 2 -> 7 -> None

After applying merge sort, what will be the final linked list? Also, what is the time complexity of merge sort on this linked list?

hard

A. 2 -> 3 -> 5 -> 7 -> 8 -> None; Time complexity: O(n log n)

B. 2 -> 3 -> 5 -> 7 -> 8 -> None; Time complexity: O(n^2)

C. 5 -> 3 -> 8 -> 2 -> 7 -> None; Time complexity: O(n log n)

D. 3 -> 2 -> 5 -> 7 -> 8 -> None; Time complexity: O(n)

Solution

1. Step 1: Sort the linked list nodes

   Sorted order is 2 -> 3 -> 5 -> 7 -> 8.

2. Step 2: Understand merge sort time complexity

   Merge sort divides list and merges in O(n log n) time for n nodes.

3. Final Answer:

   2 -> 3 -> 5 -> 7 -> 8 -> None; Time complexity: O(n log n) -> Option A

4. Quick Check:

   Sorted list + merge sort time = O(n log n) [OK]

Hint: Merge sort always sorts in O(n log n) time [OK]

Common Mistakes:

• Confusing time complexity with O(n^2)
• Not sorting nodes correctly
• Assuming merge sort is O(n)