Sort a Linked List Using Merge Sort in DSA C++ - 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 C++

struct Node {
    int val;
    Node* next;
    Node(int x) : val(x), next(nullptr) {}
};

Node* merge(Node* l1, Node* l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    if (l1->val < l2->val) {
        l1->next = merge(l1->next, l2);
        return l1;
    } else {
        l2->next = merge(l1, l2->next);
        return l2;
    }
}

Node* getMid(Node* head) {
    Node* slow = head;
    Node* fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

Node* mergeSort(Node* head) {
    if (!head || !head->next) return head;
    Node* mid = getMid(head);
    Node* rightHead = mid->next;
    mid->next = nullptr;
    Node* left = mergeSort(head);
    Node* right = mergeSort(rightHead);
    return merge(left, right);
}

void printList(Node* head) {
    while (head) {
        std::cout << head->val;
        if (head->next) std::cout << " -> ";
        head = head->next;
    }
    std::cout << " -> null" << std::endl;
}

int main() {
    Node* head = new Node(4);
    head->next = new Node(2);
    head->next->next = new Node(1);
    head->next->next->next = new Node(3);
    head = mergeSort(head);
    printList(head);
    return 0;
}

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

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

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

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

💡 Hint

Merge sort splits the list and merges sorted halves.

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

🧠 Conceptual

intermediate

Understanding the Midpoint in Merge Sort for Linked List

In the merge sort algorithm for linked lists, what is the purpose of the 'getMid' function?

A To find the last node of the list

B To find the middle node to split the list into two halves

C To reverse the linked list before sorting

D To merge two sorted linked lists

💡 Hint

Think about how merge sort divides the list.

The 'getMid' function uses slow and fast pointers to find the middle node, which helps split the list into two halves for recursive sorting.

🔧 Debug

advanced

Identify the Bug in Merge Function

What error will occur if the merge function is implemented as below? Node* merge(Node* l1, Node* l2) { if (!l1) return l2; if (!l2) return l1; if (l1->val <= l2->val) { l1->next = merge(l1->next, l2); return l1; } else { l2->next = merge(l1, l2->next); return l2; } } Assuming the input lists are sorted and non-empty.

DSA C++

Node* merge(Node* l1, Node* l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    if (l1->val <= l2->val) {
        l1->next = merge(l1->next, l2);
        return l1;
    } else {
        l2->next = merge(l1, l2->next);
        return l2;
    }
}

A Null pointer dereference error

B Stack overflow due to infinite recursion if lists contain equal values

C Memory leak due to missing delete

D No error, merges correctly

💡 Hint

Check how equal values are handled in recursion.

The merge function correctly handles equal values by choosing l1 when values are equal, so no infinite recursion occurs. It merges sorted lists properly.

❓ Predict Output

advanced

Output After Sorting a Linked List with Duplicate Values

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

DSA C++

struct Node {
    int val;
    Node* next;
    Node(int x) : val(x), next(nullptr) {}
};

Node* merge(Node* l1, Node* l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    if (l1->val < l2->val) {
        l1->next = merge(l1->next, l2);
        return l1;
    } else {
        l2->next = merge(l1, l2->next);
        return l2;
    }
}

Node* getMid(Node* head) {
    Node* slow = head;
    Node* fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

Node* mergeSort(Node* head) {
    if (!head || !head->next) return head;
    Node* mid = getMid(head);
    Node* rightHead = mid->next;
    mid->next = nullptr;
    Node* left = mergeSort(head);
    Node* right = mergeSort(rightHead);
    return merge(left, right);
}

void printList(Node* head) {
    while (head) {
        std::cout << head->val;
        if (head->next) std::cout << " -> ";
        head = head->next;
    }
    std::cout << " -> null" << std::endl;
}

int main() {
    Node* head = new Node(5);
    head->next = new Node(3);
    head->next->next = new Node(3);
    head->next->next->next = new Node(7);
    head->next->next->next->next = new Node(2);
    head = mergeSort(head);
    printList(head);
    return 0;
}

A 2 -> 3 -> 3 -> 5 -> 7 -> null

B 3 -> 3 -> 2 -> 5 -> 7 -> null

C 5 -> 3 -> 3 -> 7 -> 2 -> null

D 2 -> 3 -> 5 -> 3 -> 7 -> null

💡 Hint

Duplicates should be sorted and appear consecutively.

Merge sort sorts the list including duplicates. The sorted list is 2 -> 3 -> 3 -> 5 -> 7 -> null.

🚀 Application

expert

Time Complexity of Merge Sort on Linked List

What is the time complexity of merge sort when applied to a linked list of n nodes?

A O(log n)

B O(n^2)

C O(n log n)

D O(n)

💡 Hint

Consider how many times the list is split and merged.

Merge sort splits the list into halves log n times and merges all nodes n times per level, resulting in O(n log n) time complexity.

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