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.