Sort a Linked List Using Merge Sort in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

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

DSA C++

ListNode* findMiddle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head->next;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->[1];
        fast = fast->next->next;
    }
    return slow;
}

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

Achild

Bprev

Cnext

Drandom

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'prev' instead of 'next' causes the pointer to move backward.

Using 'child' or 'random' are invalid for singly linked lists.

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

2fill in blank

medium

Complete the code to fill in the blanks to merge two sorted linked lists.

DSA C++

ListNode* merge(ListNode* l1, ListNode* l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    if (l1->val < l2->val) {
        l1->next = merge(l1->next, [1]);
        return l1;
    } else {
        l2->next = merge([2], l2->next);
        return l2;
    }
}

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

Anullptr

Bl1

Cl2

Dhead

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping l1 and l2 in recursive calls causes wrong merges.

Using nullptr instead of the other list causes loss of nodes.

When l1->val < l2->val, recursively merge l1->next with l2 ('C'). Otherwise, merge l1 ('B') with l2->next.

3fill in blank

hard

Fix the error in the base case of the mergeSort function.

DSA C++

ListNode* mergeSort(ListNode* head) {
    if (head == nullptr || head->[1] == nullptr) {
        return head;
    }
    // rest of merge sort code
}

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

Anext

Brandom

Cchild

Dprev

Attempts:

3 left

💡 Hint

Common Mistakes

Checking head->prev is invalid for singly linked lists.

Using unrelated pointers like child or random causes errors.

The base case checks if the list has zero or one node by checking if head or head->next is nullptr.

4fill in blank

hard

Fill both blanks to split the linked list into two halves.

DSA C++

ListNode* mid = findMiddle(head);
ListNode* rightHead = mid->[1];
mid->[2] = nullptr;

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

Anext

Bprev

Cchild

Drandom

Attempts:

3 left

💡 Hint

Common Mistakes

Using prev instead of next breaks the logic in singly linked lists.

Setting the wrong pointer to nullptr causes list corruption.

To split the list, we set rightHead to mid->next and then cut the list by setting mid->next to nullptr.

5fill in blank

hard

Fill all three blanks to complete the merge sort function for linked list.

DSA C++

ListNode* mergeSort(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return head;
    ListNode* mid = [1](head);
    ListNode* rightHead = mid->[2];
    mid->next = nullptr;
    ListNode* left = mergeSort(head);
    ListNode* right = mergeSort(rightHead);
    return [3](left, right);
}

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

AfindMiddle

Bnext

Cmerge

Dsplit

Attempts:

3 left

💡 Hint

Common Mistakes

Using split instead of merge causes compilation errors.

Not setting mid->next to nullptr causes infinite recursion.

We find the middle using findMiddle, get rightHead by mid->next, and merge the sorted halves using merge.

Practice

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

easy

A. It only works for arrays, not linked lists.

B. It sorts the list in O(n^2) time but uses less memory.

C. It efficiently sorts the list in O(n log n) time without extra space for arrays.

D. It requires the list to be converted to an array first.

Solution

1. Step 1: Understand merge sort time complexity on linked lists

   Merge sort divides the list and merges sorted halves, achieving O(n log n) time.

2. Step 2: Compare space usage with other sorts

   Unlike quicksort or heapsort on arrays, merge sort on linked lists does not need extra arrays, so it uses less extra space.

3. Final Answer:

   It efficiently sorts the list in O(n log n) time without extra space for arrays. -> Option C

4. Quick Check:

   Merge sort = O(n log n) + low extra space [OK]

Hint: Merge sort is best for linked lists due to O(n log n) and no array needed [OK]

Common Mistakes:

• Thinking merge sort uses extra arrays for linked lists
• Confusing merge sort with bubble sort time complexity
• Assuming linked lists must be converted to arrays first

2. Which of the following is the correct way to split a linked list into two halves for merge sort in C++?

easy

A. Use a single pointer to count nodes and split at half index.

B. Use two pointers: slow moves 1 step, fast moves 2 steps; slow marks middle.

C. Split by dividing the node values by 2.

D. Use recursion without splitting the list.

Solution

1. Step 1: Identify the standard splitting technique

   Using two pointers, slow and fast, where fast moves twice as fast, slow ends at middle.

2. Step 2: Explain why other options are incorrect

   Counting nodes is less efficient; dividing values is meaningless; recursion needs splitting first.

3. Final Answer:

   Use two pointers: slow moves 1 step, fast moves 2 steps; slow marks middle. -> Option B

4. Quick Check:

   Two-pointer split = Use two pointers: slow moves 1 step, fast moves 2 steps; slow marks middle. [OK]

Hint: Use slow-fast pointer method to find middle in one pass [OK]

Common Mistakes:

• Trying to split by counting nodes first
• Splitting based on node values instead of positions
• Not splitting before recursive calls

3. Given the linked list: 4 -> 2 -> 1 -> 3 -> null, what is the sorted list after applying merge sort?

medium

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

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

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

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

Solution

1. Step 1: Break list into halves and sort recursively

   Split into (4 -> 2) and (1 -> 3), sort each: (2 -> 4), (1 -> 3).

2. Step 2: Merge sorted halves

   Merge (2 -> 4) and (1 -> 3) to get (1 -> 2 -> 3 -> 4).

3. Final Answer:

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

4. Quick Check:

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

Hint: Merge sort always returns ascending sorted list [OK]

Common Mistakes:

• Confusing merge order and producing descending list
• Not fully sorting both halves before merging
• Merging without comparing node values

4. In the following merge sort code for linked list, what is the bug?

Node* mergeSort(Node* head) {
  if (!head || !head->next) return head;
  Node* slow = head;
  Node* fast = head;
  while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
  }
  Node* mid = slow->next;
  slow->next = nullptr;
  Node* left = mergeSort(head);
  Node* right = mergeSort(mid);
  return merge(left, right);
}

medium

A. The base case should check only if head is nullptr.

B. Slow pointer should move twice as fast as fast pointer.

C. The merge function is called with wrong arguments.

D. Fast pointer should start at head->next, not head.

Solution

1. Step 1: Analyze pointer initialization

   Fast pointer starting at head causes incorrect middle for even length lists.

2. Step 2: Correct initialization for proper middle detection

   Fast should start at head->next to ensure slow points to middle correctly.

3. Final Answer:

   Fast pointer should start at head->next, not head. -> Option D

4. Quick Check:

   Fast pointer start = head->next [OK]

Hint: Start fast pointer at head->next to find middle correctly [OK]

Common Mistakes:

• Starting fast pointer at head causing wrong split
• Confusing slow and fast pointer speeds
• Ignoring base case for single node

5. You have a linked list with nodes containing duplicate values: 5 -> 3 -> 8 -> 3 -> 5 -> null. After applying merge sort, what will be the correct sorted linked list?

hard

A. 3 -> 3 -> 5 -> 5 -> 8 -> null

B. 5 -> 3 -> 8 -> 3 -> 5 -> null

C. 8 -> 5 -> 5 -> 3 -> 3 -> null

D. 3 -> 5 -> 8 -> 3 -> 5 -> null

Solution

1. Step 1: Understand merge sort handles duplicates by comparing values

   During merge, nodes with equal values are placed in order preserving duplicates.

2. Step 2: Sort the list step-by-step

   Sorted order is ascending: 3, 3, 5, 5, 8.

3. Final Answer:

   3 -> 3 -> 5 -> 5 -> 8 -> null -> Option A

4. Quick Check:

   Duplicates preserved and sorted ascending [OK]

Hint: Merge sort keeps duplicates and sorts ascending [OK]

Common Mistakes:

• Assuming duplicates are removed
• Sorting in descending order by mistake
• Not merging duplicates correctly