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

Practice - 5 Tasks

1fill in blank

easy

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

DSA Java

ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
    slow = slow.[1];
    fast = fast.next.next;
}

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

Achild

Bprev

Cnext

Dhead

Attempts:

3 left

💡 Hint

Common Mistakes

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

Using 'head' or 'child' are invalid references.

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

2fill in blank

medium

Complete the code to split the linked list into two halves.

DSA Java

ListNode mid = getMiddle(head);
ListNode rightHalf = mid.[1];
mid.next = null;

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

Aprev

Bnext

Cchild

Dhead

Attempts:

3 left

💡 Hint

Common Mistakes

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

Using 'head' or 'child' are invalid references.

The right half starts from the node after mid, so we use 'next'.

3fill in blank

hard

Fix the error in the merge function to correctly merge two sorted lists.

DSA Java

if (l1.val < l2.val) {
    result = l1;
    result.next = merge(l1.next, [1]);
} else {
    result = l2;
    result.next = merge([2], l2.next);
}

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

Al1

Bl2

Cnull

Dhead

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping l1 and l2 in recursive calls causes incorrect merges.

Using 'null' or 'head' breaks the recursion.

When l1.val < l2.val, we merge the rest starting from l1.next and l2.

4fill in blank

hard

Fill both blanks to complete the base case check in merge sort.

DSA Java

if (head == null || head.[1] == [2]) {
    return head;
}

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

Anext

Bprev

Cnull

Dhead

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'prev' instead of 'next' causes errors.

Comparing to 'head' instead of 'null' is incorrect.

The base case returns when the list is empty or has one node (next is null).

5fill in blank

hard

Fill all three blanks to complete the merge sort function.

DSA Java

ListNode mid = [1](head);
ListNode right = mid.[2];
mid.next = null;
ListNode leftSorted = mergeSort(head);
ListNode rightSorted = mergeSort(right);
return [3](leftSorted, rightSorted);

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

AgetMiddle

Bnext

Cmerge

Dsort

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong function names causes errors.

Not splitting the list properly breaks recursion.

We get the middle node, split at next, then merge sorted halves.

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