Sort a Linked List Using Merge Sort in DSA Java - 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, sorts each half recursively, 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 efficiently for merge sort?

Use two pointers: a slow pointer that moves one step at a time and a fast pointer that moves two steps at a time. 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 the merge step works in merge sort for linked lists.

The merge step takes two sorted linked lists and combines them into one sorted linked list by repeatedly choosing the smaller head node from the two lists and linking it to the result.

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

A Random access to middle index

B Counting nodes then dividing by two

C Two pointers: slow and fast

D Using a stack to store nodes

Two pointers, slow and fast, are used to find the middle efficiently without counting all nodes.

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

A O(n log n)

B O(log n)

C O(n^2)

D O(n)

Merge sort always 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 uses less memory

C Quicksort is faster on linked lists

D Merge sort does not require random access

Merge sort works well because it does not need random access, which linked lists lack.

During the merge step, how do you decide which node to add next?

A Choose the node with the larger value

B Choose the node with the smaller value

C Choose nodes alternately from each list

D Choose nodes randomly

You always pick the smaller node to keep the merged list sorted.

What happens when the fast pointer reaches the end of the list in the middle-finding step?

A Slow pointer is at the middle

B Fast pointer resets to head

C List is reversed

D Algorithm stops without middle

When fast pointer reaches the end, slow pointer points to the middle node.

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

Think about splitting, sorting, and merging.

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

Consider linked list properties and merge sort advantages.

Practice

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

easy

A. Merge sort is easier to implement with arrays than linked lists.

B. Quicksort is faster on linked lists because it uses less memory.

C. Merge sort does not require random access and works well with linked lists.

D. Quicksort always sorts linked lists in O(n) time.

Solution

1. Step 1: Understand linked list access

   Linked lists do not support fast random access, so algorithms needing it perform poorly.

2. Step 2: Compare merge sort and quicksort

   Merge sort splits and merges lists using pointers, avoiding random access, making it efficient for linked lists.

3. Final Answer:

   Merge sort does not require random access and works well with linked lists. -> Option C

4. Quick Check:

   Merge sort suits linked lists better than quicksort [OK]

Hint: Merge sort fits linked lists due to pointer-based splitting [OK]

Common Mistakes:

• Thinking quicksort is always faster on linked lists
• Assuming arrays and linked lists behave the same
• Ignoring random access needs

2. Which of the following is the correct base case condition in the merge sort function for a linked list?

easy

A. if (head == null) return head.next;

B. if (head == null || head.next == null) return head;

C. if (head.next == null) return null;

D. if (head == null && head.next == null) return null;

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: Check condition correctness

   Condition 'head == null || head.next == null' correctly checks for empty or single-node list.

3. Final Answer:

   if (head == null || head.next == null) return head; -> Option B

4. Quick Check:

   Base case returns head if list size ≤ 1 [OK]

Hint: Base case: empty or single node list returns itself [OK]

Common Mistakes:

• Using && instead of || in base case
• Returning null incorrectly for single node
• Not handling empty list properly

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

medium

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

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

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

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

Solution

1. Step 1: Split the list into halves

   Split into (4 -> 2) and (1 -> 3).

2. Step 2: Recursively sort halves 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 -> null -> Option A

4. Quick Check:

   Sorted list ascending order [OK]

Hint: Merge sorted halves to get fully sorted list [OK]

Common Mistakes:

• Not splitting list correctly
• Merging without sorting halves
• Mixing node order during merge

4. Identify the error in this merge function snippet for linked lists:

Node merge(Node a, Node b) {
  if (a == null) return b;
  if (b == null) return a;
  if (a.data < b.data) {
    a.next = merge(a.next, b);
    return b;
  } else {
    b.next = merge(a, b.next);
    return a;
  }
}

medium

A. The function does not merge nodes recursively.

B. The base cases do not handle null nodes.

C. The comparison operator should be <= instead of <.

D. The function returns the wrong node after recursion.

Solution

1. Step 1: Analyze return statements

   When a.data < b.data, function should return 'a' but returns 'b' incorrectly.

2. Step 2: Correct return node after recursion

   Return the node chosen as smaller to maintain sorted order; here it should be 'a' or 'b' accordingly.

3. Final Answer:

   The function returns the wrong node after recursion. -> Option D

4. Quick Check:

   Return chosen smaller node to merge correctly [OK]

Hint: Return the smaller node after recursive merge [OK]

Common Mistakes:

• Returning wrong node after recursive call
• Ignoring base cases
• Incorrect comparison operator

5. You have a linked list with nodes: 5 -> 3 -> 8 -> 2 -> 7 -> null. After applying merge sort, what is the correct sorted linked list? Also, explain why merge sort is preferred over bubble sort for this linked list.

hard

A. 2 -> 3 -> 5 -> 7 -> 8 -> null; Merge sort is faster and uses less memory on linked lists.

B. 8 -> 7 -> 5 -> 3 -> 2 -> null; Bubble sort is faster for small lists.

C. 2 -> 3 -> 5 -> 7 -> 8 -> null; Bubble sort is preferred because it is simpler.

D. 5 -> 3 -> 8 -> 2 -> 7 -> null; Merge sort does not work on linked lists.

Solution

1. Step 1: Sort the list using merge sort

   Sorted order is 2 -> 3 -> 5 -> 7 -> 8 -> null after splitting and merging.

2. Step 2: Explain merge sort advantage

   Merge sort is O(n log n) and uses pointers efficiently; bubble sort is O(n²) and inefficient for linked lists.

3. Final Answer:

   2 -> 3 -> 5 -> 7 -> 8 -> null; Merge sort is faster and uses less memory on linked lists. -> Option A

4. Quick Check:

   Sorted list + merge sort efficiency [OK]

Hint: Merge sort is efficient and stable for linked lists [OK]

Common Mistakes:

• Confusing bubble sort as faster
• Incorrect sorted order
• Thinking merge sort can't handle linked lists