Merge Two Sorted Linked Lists in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output after merging two sorted linked lists?

Given two sorted linked lists:
List1: 1 -> 3 -> 5 -> null
List2: 2 -> 4 -> 6 -> null
What is the merged linked list?

DSA Javascript

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

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

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

let merged = mergeTwoLists(l1, l2);

// Function to print list
function printList(head) {
  let result = [];
  while (head !== null) {
    result.push(head.val);
    head = head.next;
  }
  return result.join(' -> ') + ' -> null';
}

console.log(printList(merged));

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

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

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

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

💡 Hint

Compare nodes one by one and attach the smaller node to the merged list.

The function compares the current nodes of both lists and attaches the smaller one to the merged list, continuing until all nodes are merged in sorted order.

❓ Predict Output

intermediate

What is the output of merging when one list is empty?

Given two linked lists:
List1: null
List2: 0 -> 1 -> 2 -> null
What is the merged linked list?

DSA Javascript

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

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

// Construct lists
let l1 = null;
let l2 = new ListNode(0, new ListNode(1, new ListNode(2)));

let merged = mergeTwoLists(l1, l2);

// Function to print list
function printList(head) {
  let result = [];
  while (head !== null) {
    result.push(head.val);
    head = head.next;
  }
  return result.join(' -> ') + ' -> null';
}

console.log(printList(merged));

A 1 -> 2 -> null

B null

C 0 -> null

D 0 -> 1 -> 2 -> null

💡 Hint

If one list is empty, the merged list is just the other list.

Since the first list is empty, the merged list is simply the second list unchanged.

🔧 Debug

advanced

Why does this merge function cause an infinite loop?

Consider this merge function for two sorted linked lists. It causes an infinite loop. Why?

function mergeTwoLists(l1, l2) { let dummy = new ListNode(0); let current = dummy; while (l1 !== null && l2 !== null) { if (l1.val < l2.val) { current.next = l1; l1 = l1.next; } else { current.next = l2; l2 = l2.next; } // Missing current = current.next here } current.next = l1 !== null ? l1 : l2; return dummy.next; }

A The pointer 'current' is never moved forward, so the loop keeps attaching the same node causing infinite loop.

B The function does not handle empty lists, causing infinite loop.

C The condition in while loop is incorrect, should be '||' instead of '&&'.

D The dummy node is not initialized properly causing infinite loop.

💡 Hint

Check if the 'current' pointer moves forward inside the loop.

The 'current' pointer must move forward after attaching a node. Without 'current = current.next', the same node is attached repeatedly causing infinite loop.

🧠 Conceptual

advanced

What is the time complexity of merging two sorted linked lists of lengths m and n?

You have two sorted linked lists with lengths m and n. What is the time complexity of merging them into one sorted linked list?

A O(m + n)

B O(m * n)

C O(max(m, n)^2)

D O(log(m + n))

💡 Hint

Each node is visited once during merging.

The merge process visits each node exactly once, so the time complexity is linear in the total number of nodes.

❓ Predict Output

expert

What is the output after merging two sorted linked lists with duplicate values?

Given two sorted linked lists:
List1: 1 -> 3 -> 5 -> 7 -> null
List2: 1 -> 2 -> 5 -> 6 -> null
What is the merged linked list?

DSA Javascript

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

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

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

let merged = mergeTwoLists(l1, l2);

// Function to print list
function printList(head) {
  let result = [];
  while (head !== null) {
    result.push(head.val);
    head = head.next;
  }
  return result.join(' -> ') + ' -> null';
}

console.log(printList(merged));

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

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

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

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

💡 Hint

Duplicates are allowed and merged in sorted order.

The merge function includes duplicates and maintains sorted order by choosing the smaller or equal node first.

Practice

1. What is the main goal when merging two sorted linked lists?

easy

A. To find the largest element in both lists

B. To reverse both linked lists

C. To create a new sorted linked list containing all elements from both lists

D. To delete duplicate elements from both lists

Solution

1. Step 1: Understand the merging process

   Merging means combining two lists into one while keeping the order sorted.

2. Step 2: Identify the goal of merging sorted lists

   The goal is to create a new sorted list that contains all elements from both lists without changing their order.

3. Final Answer:

   To create a new sorted linked list containing all elements from both lists -> Option C

4. Quick Check:

   Merging = combining sorted lists [OK]

Hint: Merging means combining sorted lists into one sorted list [OK]

Common Mistakes:

• Thinking merging reverses the lists
• Confusing merging with finding max element
• Assuming duplicates are removed automatically

2. Which of the following is the correct way to start merging two sorted linked lists in JavaScript?

easy

A. let dummy = new ListNode(0); let current = dummy;

B. let dummy = new ListNode(); let current = dummy.next;

C. let dummy = 0; let current = dummy;

D. let current = null; let dummy = current;

Solution

1. Step 1: Initialize a dummy node correctly

   We create a dummy node with a value (usually 0) to start the merged list.

2. Step 2: Set a pointer to track the current node

   We set current to dummy to build the merged list from dummy onwards.

3. Final Answer:

   let dummy = new ListNode(0); let current = dummy; -> Option A

4. Quick Check:

   Dummy node initialization = let dummy = new ListNode(0); let current = dummy; [OK]

Hint: Start with dummy node and current pointer for easy list building [OK]

Common Mistakes:

• Using primitive 0 instead of ListNode object
• Swapping dummy and current incorrectly
• Setting current or dummy to null initially

3. What will be the merged linked list after running the following code?

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

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

function mergeTwoLists(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;
}

let merged = mergeTwoLists(l1, l2);

let result = [];
while (merged) {
  result.push(merged.val);
  merged = merged.next;
}
console.log(result);

medium

A. [1, 3, 5, 2, 4, 6]

B. [1, 2, 3, 4, 5, 6]

C. [2, 4, 6, 1, 3, 5]

D. [6, 5, 4, 3, 2, 1]

Solution

1. Step 1: Trace the merging loop

   Compare nodes: 1 < 2, add 1; 3 > 2, add 2; 3 < 4, add 3; 5 > 4, add 4; 5 < 6, add 5; then add remaining 6.

2. Step 2: Collect merged list values

   The merged list values in order are [1, 2, 3, 4, 5, 6].

3. Final Answer:

   [1, 2, 3, 4, 5, 6] -> Option B

4. Quick Check:

   Sorted merge result = [1, 2, 3, 4, 5, 6] [OK]

Hint: Compare heads, pick smaller, move pointer, repeat [OK]

Common Mistakes:

• Appending entire list instead of node by node
• Not updating current pointer after adding node
• Mixing order of nodes in merged list

4. Identify the bug in this merge function and select the fix:

function mergeTwoLists(l1, l2) {
  let dummy = new ListNode(0);
  let current = dummy;
  while (l1 !== null || l2 !== null) {
    if (l1.val < l2.val) {
      current.next = l1;
      l1 = l1.next;
    } else {
      current.next = l2;
      l2 = l2.next;
    }
    current = current.next;
  }
  return dummy.next;
}

medium

A. Initialize dummy with null instead of 0

B. Add check for null before comparing l1.val and l2.val

C. Remove current = current.next inside the loop

D. Change while condition to 'while (l1 && l2)'

Solution

1. Step 1: Analyze the while loop condition

   The loop uses '||' which allows l1 or l2 to be null, causing errors when accessing val.

2. Step 2: Fix the loop condition

   Changing the condition to 'while (l1 && l2)' ensures both lists have nodes before accessing val.

3. Final Answer:

   Change while condition to 'while (l1 && l2)' -> Option D

4. Quick Check:

   Loop condition with && prevents null pointer errors [OK]

Hint: Use && in loop condition to ensure both nodes exist before access [OK]

Common Mistakes:

• Using || instead of && in loop condition without null checks
• Forgetting to move current pointer
• Initializing dummy with wrong value type

5. Given two sorted linked lists where one is empty and the other is 1 -> 2 -> 3 -> null, what is the merged list?

medium

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

B. Error due to empty list

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

D. null

Solution

1. Step 1: Understand merging with an empty list

   If one list is empty, the merged list is just the other list unchanged.

2. Step 2: Apply this to given lists

   Since one list is empty and the other is 1 -> 2 -> 3 -> null, the merged list is 1 -> 2 -> 3 -> null.

3. Final Answer:

   1 -> 2 -> 3 -> null -> Option A

4. Quick Check:

   Merging with empty list returns the non-empty list [OK]

Hint: Empty list merged with sorted list returns the sorted list [OK]

Common Mistakes:

• Assuming error occurs when one list is empty
• Reversing the non-empty list mistakenly
• Returning null instead of the non-empty list