Sort a Linked List Using Merge Sort in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to find the middle node of the linked list.

DSA Python

def get_middle(head):
    if head is None:
        return head
    slow = head
    fast = head.next
    while fast and fast.next:
        slow = slow.[1]
        fast = fast.next.next
    return slow

Drag options to blanks, or click blank then click option'

Arandom

Bprev

Cchild

Dnext

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'prev' instead of 'next' causes errors because singly linked lists don't have 'prev'.

Using 'fast.next' instead of 'fast.next.next' for the fast pointer.

The slow pointer moves one step at a time using the 'next' attribute to find the middle node.

2fill in blank

medium

Complete the code to merge two sorted linked lists.

DSA Python

def merge_sorted_lists(l1, l2):
    dummy = ListNode(0)
    tail = dummy
    while l1 and l2:
        if l1.val < l2.val:
            tail.next = l1
            l1 = l1.[1]
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next
    tail.next = l1 or l2
    return dummy.next

Drag options to blanks, or click blank then click option'

Anext

Bprev

Cchild

Drandom

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'prev' which does not exist in singly linked lists.

Using 'child' or 'random' which are not standard pointers.

To move forward in the linked list l1, we use l1.next.

3fill in blank

hard

Fix the error in the merge_sort function to correctly split the list.

DSA Python

def merge_sort(head):
    if not head or not head.next:
        return head
    middle = get_middle(head)
    next_to_middle = middle.next
    middle.[1] = None
    left = merge_sort(head)
    right = merge_sort(next_to_middle)
    sorted_list = merge_sorted_lists(left, right)
    return sorted_list

Drag options to blanks, or click blank then click option'

Anext

Bprev

Cchild

Drandom

Attempts:

3 left

💡 Hint

Common Mistakes

Setting middle.prev which does not exist in singly linked lists.

Not breaking the list, causing infinite recursion.

To split the list, we set middle.next to None to break the list into two halves.

4fill in blank

hard

Fill both blanks to create a dictionary of word lengths for words longer than 3 characters.

DSA Python

words = ['apple', 'bat', 'carrot', 'dog', 'elephant']
lengths = {word: [1] for word in words if len(word) [2] 3}

Drag options to blanks, or click blank then click option'

Alen(word)

B>

C<

Dword

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '>' causing wrong filtering.

Using 'word' instead of 'len(word)' for dictionary values.

We use len(word) to get the length and '>' to filter words longer than 3.

5fill in blank

hard

Fill all three blanks to create a dictionary with uppercase keys and values greater than 0.

DSA Python

data = {'a': 1, 'b': 0, 'c': 3}
result = { [1] : [2] for k, v in data.items() if v [3] 0 }

Drag options to blanks, or click blank then click option'

Ak.upper()

Bv

C>

Dk

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'k' instead of 'k.upper()' for keys.

Using '<' instead of '>' for filtering values.

Keys are converted to uppercase with k.upper(), values are v, and filter uses '>' to keep values greater than 0.

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)