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

Practice - 5 Tasks

1fill in blank

easy

Complete the code to find the middle node of the linked list using the fast and slow pointer technique.

DSA Javascript

function findMiddle(head) {
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.[1];
    fast = fast.next.next;
  }
  return slow;
}

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

Aprev

Bnext

Chead

Dvalue

Attempts:

3 left

💡 Hint

Common Mistakes

Using fast pointer's next instead of slow pointer's next.

Using prev instead of next for slow pointer.

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

2fill in blank

medium

Complete the code to merge two sorted linked lists into one sorted list.

DSA Javascript

function mergeLists(l1, l2) {
  let dummy = new ListNode(0);
  let current = dummy;
  while (l1 !== null && l2 !== null) {
    if (l1.value < l2.value) {
      current.next = l1;
      l1 = l1.[1];
    } else {
      current.next = l2;
      l2 = l2.next;
    }
    current = current.next;
  }
  current.next = l1 !== null ? l1 : l2;
  return dummy.next;
}

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

Aprev

Bvalue

Chead

Dnext

Attempts:

3 left

💡 Hint

Common Mistakes

Using prev instead of next.

Using value instead of next.

To move forward in the list, we use the next property.

3fill in blank

hard

Fix the error in the base case check of the merge sort function for linked list.

DSA Javascript

function mergeSort(head) {
  if (head === null || head.[1] === null) {
    return head;
  }
  // rest of merge sort logic
}

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

Aprev

Bvalue

Cnext

Dhead

Attempts:

3 left

💡 Hint

Common Mistakes

Checking head.prev instead of head.next.

Checking head.value instead of head.next.

The base case checks if the list is empty or has only one node by checking head.next.

4fill in blank

hard

Fill both blanks to split the linked list into two halves and recursively sort them.

DSA Javascript

function mergeSort(head) {
  if (head === null || head.next === null) return head;
  let middle = findMiddle(head);
  let nextToMiddle = middle.[1];
  middle.[2] = null;
  let left = mergeSort(head);
  let right = mergeSort(nextToMiddle);
  return mergeLists(left, right);
}

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

Anext

Bprev

Cvalue

Dhead

Attempts:

3 left

💡 Hint

Common Mistakes

Using prev instead of next.

Not breaking the list by setting middle.next to null.

We use next to get the node after middle and to break the list by setting middle.next = null.

5fill in blank

hard

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

DSA Javascript

function mergeSort(head) {
  if (head === null || head.next === null) return head;
  let middle = [1](head);
  let nextToMiddle = middle.[2];
  middle.[3] = null;
  let left = mergeSort(head);
  let right = mergeSort(nextToMiddle);
  return mergeLists(left, right);
}

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

AfindMiddle

Bnext

DmergeLists

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong function name instead of findMiddle.

Using prev instead of next.

Not breaking the list by setting middle.next to null.

We call findMiddle to get the middle node, use next to get the node after middle, and set middle.next = null to split the list.

Practice

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

easy

A. Merge sort uses less memory than bubble sort for arrays.

B. Merge sort efficiently handles linked lists without random access.

C. Merge sort sorts elements in place without extra space.

D. Merge sort is the fastest sorting algorithm for small arrays.

Solution

1. Step 1: Understand linked list access

   Linked lists do not support random access, so algorithms relying on index access are inefficient.

2. Step 2: Analyze merge sort suitability

   Merge sort works by splitting and merging lists using pointers, which fits linked lists well without needing random access.

3. Final Answer:

   Merge sort efficiently handles linked lists without random access. -> Option B

4. Quick Check:

   Linked list + merge sort = efficient pointer-based sorting [OK]

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

Common Mistakes:

• Thinking merge sort sorts in place for linked lists
• Confusing merge sort speed with bubble sort
• Assuming random access is needed for merge sort

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

easy

A. Use a for loop to iterate half the length and split at midpoint index.

B. Use array slicing to split the linked list into two arrays.

C. Use recursion to split the list by removing the head each time.

D. Use two pointers: slow moves 1 step, fast moves 2 steps until fast reaches end.

Solution

1. Step 1: Identify splitting method for linked list

   Since linked lists lack indexes, we use two pointers: slow and fast to find midpoint.

2. Step 2: Explain pointer movement

   Slow pointer moves one node at a time, fast pointer moves two nodes; when fast reaches end, slow is at midpoint.

3. Final Answer:

   Use two pointers: slow moves 1 step, fast moves 2 steps until fast reaches end. -> Option D

4. Quick Check:

   Two-pointer technique splits linked list correctly [OK]

Hint: Use slow/fast pointers to find midpoint in linked list [OK]

Common Mistakes:

• Trying to use array methods on linked lists
• Using loops with indexes on linked lists
• Splitting by removing head repeatedly

3. What will be the output linked list after applying merge sort on the list: 4 -> 2 -> 1 -> 3 -> null?

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: Split the list into halves

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

2. Step 2: Recursively sort and merge halves

   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 ascending list = 1->2->3->4 [OK]

Hint: Merge sort outputs sorted ascending linked list [OK]

Common Mistakes:

• Confusing merge order and producing descending list
• Not fully sorting sublists before merging
• Incorrectly splitting the list

4. Given this merge sort code snippet for linked lists, what is the bug?

function mergeSort(head) {
  if (!head || !head.next) return head;
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  let mid = slow.next;
  slow.next = null;
  let left = mergeSort(head);
  let right = mergeSort(mid);
  return merge(left, right);
}

medium

A. The mid pointer should be slow, not slow.next.

B. Slow pointer should start at head.next, not head.

C. Fast pointer should start at head.next, not head.

D. The base case should check only for head.next, not head.

Solution

1. Step 1: Analyze pointer initialization

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

2. Step 2: Correct mid pointer assignment

   The mid pointer should be slow, not slow.next, to correctly split the list into two halves.

3. Final Answer:

   The mid pointer should be slow, not slow.next. -> Option A

4. Quick Check:

   Mid pointer assignment = slow for correct split [OK]

Hint: Mid pointer must be slow for correct split [OK]

Common Mistakes:

• Starting fast pointer at head
• Misplacing mid pointer assignment
• Incorrect base case conditions

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

hard

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

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

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

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

Solution

1. Step 1: Understand merge sort handles duplicates

   Merge sort compares node values and merges them in ascending order, preserving duplicates.

2. Step 2: Sort and merge duplicates

   Sorting 3->1->2->3->2 results in 1->2->2->3->3 as duplicates remain in sorted order.

3. Final Answer:

   1 -> 2 -> 2 -> 3 -> 3 -> null -> Option C

4. Quick Check:

   Duplicates sorted and preserved in ascending order [OK]

Hint: Merge sort keeps duplicates sorted in order [OK]

Common Mistakes:

• Removing duplicates by mistake
• Sorting incorrectly in descending order
• Confusing linked list with array sorting