Sort a Linked List Using Merge Sort in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind merge sort when sorting a linked list?

Merge sort divides the linked list into two halves, recursively sorts each half, and then merges the two sorted halves back together.

intermediate

Why is merge sort preferred over quicksort for sorting linked lists?

Merge sort works well with linked lists because it does not require random access and can merge two sorted lists efficiently, while quicksort relies on random access which linked lists do not support efficiently.

beginner

How do you find the middle of a linked list to split it for merge sort?

Use two pointers: a slow pointer that moves one step at a time and a fast pointer that moves two steps. When the fast pointer reaches the end, the slow pointer will be at the middle.

beginner

What is the time complexity of merge sort on a linked list?

The time complexity is O(n log n), where n is the number of nodes in the linked list.

beginner

Explain how merging two sorted linked lists works in merge sort.

Compare the first nodes of both lists, attach the smaller one to the result, and move its pointer forward. Repeat until all nodes are merged into a single sorted list.

What technique is used to find the middle of a linked list in merge sort?

A Two pointers: slow and fast

B Counting nodes then dividing by two

C Using a stack

D Random access indexing

Two pointers technique is efficient and commonly used to find the middle without counting all nodes.

What is the best time complexity of merge sort on a linked list?

A O(n^2)

B O(n)

C O(log n)

D O(n log n)

Merge sort consistently runs in O(n log n) time for linked lists.

Why is merge sort suitable for linked lists compared to quicksort?

A Merge sort uses random access

B Quicksort is faster on linked lists

C Merge sort does not require random access

D Quicksort uses less memory

Linked lists do not support random access efficiently, so merge sort is preferred.

What happens after splitting the linked list in merge sort?

A The halves are merged immediately

B The halves are sorted recursively

C The halves are discarded

D The halves are reversed

Each half is sorted recursively before merging.

How do you merge two sorted linked lists?

A By comparing nodes and linking the smaller one first

B By concatenating the lists

C By reversing both lists

D By sorting each list again

Merging involves comparing nodes and linking the smaller node first to maintain order.

Describe the steps to sort a linked list using merge sort.

Think about dividing, sorting, and combining.

Explain why merge sort is efficient for linked lists compared to other sorting algorithms.

Consider how linked lists store data and how merge sort uses that.

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