Merge Two Sorted Linked Lists in DSA Javascript

Mental Model

We combine two sorted lists into one sorted list by picking the smallest item from the front of either list step by step.

Analogy: Imagine two lines of people sorted by height waiting to enter a room. We let in the shortest person from the front of either line one by one to keep the final line sorted.

List1: 1 -> 3 -> 5 -> null
List2: 2 -> 4 -> 6 -> null
Merged: null

Dry Run Walkthrough

Input: list1: 1 -> 3 -> 5, list2: 2 -> 4 -> 6

Goal: Create one sorted list containing all elements from both lists in order

Step 1: Compare heads: 1 (list1) and 2 (list2), pick 1

Merged: 1 -> null
List1: 3 -> 5 -> null
List2: 2 -> 4 -> 6 -> null

Why: 1 is smaller, so it goes first to keep merged list sorted

Step 2: Compare heads: 3 (list1) and 2 (list2), pick 2

Merged: 1 -> 2 -> null
List1: 3 -> 5 -> null
List2: 4 -> 6 -> null

Why: 2 is smaller, so it goes next

Step 3: Compare heads: 3 (list1) and 4 (list2), pick 3

Merged: 1 -> 2 -> 3 -> null
List1: 5 -> null
List2: 4 -> 6 -> null

Why: 3 is smaller, so it goes next

Step 4: Compare heads: 5 (list1) and 4 (list2), pick 4

Merged: 1 -> 2 -> 3 -> 4 -> null
List1: 5 -> null
List2: 6 -> null

Why: 4 is smaller, so it goes next

Step 5: Compare heads: 5 (list1) and 6 (list2), pick 5

Merged: 1 -> 2 -> 3 -> 4 -> 5 -> null
List1: null
List2: 6 -> null

Why: 5 is smaller, so it goes next

Step 6: List1 empty, append remaining list2 nodes

Merged: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
List1: null
List2: null

Why: No more nodes in list1, so add all remaining nodes from list2

Result:

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

Annotated Code

DSA Javascript

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

function mergeTwoSortedLists(list1, list2) {
  const dummy = new ListNode();
  let current = dummy;

  while (list1 !== null && list2 !== null) {
    if (list1.val < list2.val) {
      current.next = list1; // attach smaller node
      list1 = list1.next;   // move list1 forward
    } else {
      current.next = list2; // attach smaller or equal node
      list2 = list2.next;   // move list2 forward
    }
    current = current.next; // move current forward
  }

  // attach remaining nodes if any
  current.next = list1 !== null ? list1 : list2;

  return dummy.next;
}

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

// Driver code using dry_run input
const l1 = new ListNode(1, new ListNode(3, new ListNode(5)));
const l2 = new ListNode(2, new ListNode(4, new ListNode(6)));
const merged = mergeTwoSortedLists(l1, l2);
console.log(printList(merged));

while (list1 !== null && list2 !== null) {

continue merging while both lists have nodes

if (list1.val < list2.val) {

choose smaller node from list1 or list2

current.next = list1;

attach smaller node from list1 to merged list

list1 = list1.next;

move list1 pointer forward

current.next = list2;

attach smaller or equal node from list2 to merged list

list2 = list2.next;

move list2 pointer forward

current = current.next;

advance current pointer in merged list

current.next = list1 !== null ? list1 : list2;

attach remaining nodes after one list is empty

Output

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

Complexity Analysis

Time: O(n + m) because we visit each node from both lists once

Space: O(1) because we only use a few pointers and reuse existing nodes

vs Alternative: Compared to creating a new list and copying nodes, this approach is faster and uses less memory by reusing nodes

Edge Cases

One or both lists are empty

Returns the non-empty list or null if both empty

DSA Javascript

while (list1 !== null && list2 !== null) {

Lists with duplicate values

Duplicates are merged in order, preserving sorting

DSA Javascript

if (list1.val < list2.val) {

Lists of different lengths

Remaining nodes of longer list are appended after shorter list ends

DSA Javascript

current.next = list1 !== null ? list1 : list2;

When to Use This Pattern

When you see two sorted linked lists and need one sorted list, use the merge pattern by comparing heads and building the result step by step.

Common Mistakes

Mistake: Forgetting to move the pointer of the list from which a node was taken
Fix: Always advance the pointer of the list after attaching its node

Mistake: Not attaching the remaining nodes after one list ends
Fix: Attach leftover nodes after the main loop ends

Mistake: Modifying input lists incorrectly or losing references
Fix: Use a dummy node and carefully update pointers without losing nodes

Summary

It merges two sorted linked lists into one sorted linked list.

Use it when you need to combine two sorted lists efficiently.

The key is to pick the smaller head node from either list repeatedly until all nodes are merged.

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