Sort a Linked List Using Merge Sort in DSA Javascript - 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 sorting it using merge sort?

Initial linked list: 4 -> 2 -> 1 -> 3 -> null

DSA Javascript

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function mergeSort(head) {
  if (!head || !head.next) return head;

  // Find middle
  let slow = head, fast = head.next;
  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);
}

function merge(l1, l2) {
  let dummy = new ListNode(0);
  let current = dummy;

  while (l1 && l2) {
    if (l1.val < l2.val) {
      current.next = l1;
      l1 = l1.next;
    } else {
      current.next = l2;
      l2 = l2.next;
    }
    current = current.next;
  }

  current.next = l1 || l2;
  return dummy.next;
}

// Create linked list 4 -> 2 -> 1 -> 3 -> null
let head = new ListNode(4, new ListNode(2, new ListNode(1, new ListNode(3))));

// Sort
head = mergeSort(head);

// Print sorted list
let result = [];
while (head) {
  result.push(head.val);
  head = head.next;
}
console.log(result.join(' -> ') + ' -> null');

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

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

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

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

💡 Hint

Think about how merge sort splits and merges the list in sorted order.

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

❓ Predict Output

intermediate

Result of Merging Two Sorted Linked Lists

What is the printed state of the linked list after merging these two sorted lists?

List 1: 1 -> 3 -> 5 -> null
List 2: 2 -> 4 -> 6 -> null

DSA Javascript

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function merge(l1, l2) {
  let dummy = new ListNode(0);
  let current = dummy;

  while (l1 && l2) {
    if (l1.val < l2.val) {
      current.next = l1;
      l1 = l1.next;
    } else {
      current.next = l2;
      l2 = l2.next;
    }
    current = current.next;
  }

  current.next = l1 || l2;
  return dummy.next;
}

// Create lists
let l1 = new ListNode(1, new ListNode(3, new ListNode(5)));
let l2 = new ListNode(2, new ListNode(4, new ListNode(6)));

// Merge
let merged = merge(l1, l2);

// Print merged list
let result = [];
while (merged) {
  result.push(merged.val);
  merged = merged.next;
}
console.log(result.join(' -> ') + ' -> null');

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

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

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

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

💡 Hint

Merging two sorted lists results in a sorted combined list.

The merge function compares nodes from both lists and links them in ascending order, producing a fully sorted merged list.

🧠 Conceptual

advanced

Why Use Merge Sort for Linked Lists?

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

A Because merge sort uses less memory but requires random access.

B Because quicksort is faster but uses more memory for linked lists.

C Because merge sort does not require random access and works efficiently with linked lists.

D Because quicksort is stable and merge sort is not.

💡 Hint

Think about how linked lists store elements and how merge sort accesses them.

Merge sort works well with linked lists because it only needs sequential access and can split and merge lists efficiently without random access. Quicksort requires random access which linked lists do not support efficiently.

🔧 Debug

advanced

Identify the Bug in Merge Sort Implementation

What is the bug in this merge sort code for linked lists?

Code snippet:
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); }

A The fast pointer should start at head.next to correctly find the middle.

B The slow pointer should start at head.next instead of head.

C The base case should check only if head is null, not head.next.

D The merge function is missing and causes the bug.

💡 Hint

Check how the middle node is found using slow and fast pointers.

Starting fast at head.next ensures the slow pointer stops at the node before the middle, correctly splitting the list. Starting fast at head causes incorrect splitting for even-length lists.

🚀 Application

expert

Number of Recursive Calls in Merge Sort on Linked List

Given a linked list of 8 nodes, how many total recursive calls to mergeSort are made during the full sort process?

A 7

B 8

C 16

D 15

💡 Hint

Think about how merge sort splits the list into halves recursively until single nodes.

Merge sort splits the list into halves until single nodes remain. For 8 nodes, the recursion tree has 15 calls (7 internal nodes + 8 leaves).

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