Merge Two Sorted Linked Lists in DSA Javascript - Deep Dive

Overview - Merge Two Sorted Linked Lists

What is it?

Merging two sorted linked lists means combining them into one sorted linked list. Each input list is already sorted from smallest to largest. The goal is to create a sorted linked list that maintains this order by reusing nodes from both input lists. This helps organize data efficiently when combining two sorted sequences.

Why it matters

Without merging sorted lists, combining data would be slow and messy, requiring extra sorting steps. Merging keeps data organized and speeds up tasks like searching or processing. It is a key step in many algorithms, like sorting large datasets or managing streams of data in real time.

Where it fits

Before learning this, you should understand what linked lists are and how to traverse them. After this, you can learn about more complex list operations, sorting algorithms like merge sort, and how to handle data streams efficiently.

Mental Model

Core Idea

Merging two sorted linked lists means walking through both lists together, always picking the smaller current item to build a new sorted list.

Think of it like...

Imagine two friends lining up in order of height for a photo. You take turns picking the shorter person from the front of each line to form one new line, keeping everyone in height order.

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

Merge process:
Start: Compare 1 and 2 -> pick 1
Next: Compare 3 and 2 -> pick 2
Next: Compare 3 and 4 -> pick 3
Next: Compare 5 and 4 -> pick 4
Next: Compare 5 and 6 -> pick 5
End: Append remaining 6

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

Build-Up - 7 Steps

1

Foundation

Understanding Linked List Structure

Concept: Learn what a linked list node is and how nodes connect to form a list.

A linked list is made of nodes. Each node holds a value and a link to the next node. The last node points to null, meaning the list ends there. For example, a node with value 1 pointing to a node with value 2 looks like: 1 -> 2 -> null.

Result

You can represent a sequence of values connected by links, allowing easy insertion and traversal.

Knowing the basic building block of linked lists is essential before manipulating or merging them.

2

Foundation

Traversing a Linked List

Concept: Learn how to move through a linked list from start to end.

Start at the head node. Visit its value, then move to the next node using the link. Repeat until you reach null. For example, to print all values: start at head, print value, move to next, stop at null.

Result

You can read or process all elements in a linked list in order.

Traversal is the foundation for comparing and merging nodes from two lists.

3

Intermediate

Comparing Nodes from Two Lists

🤔Before reading on: When merging, do you think you should pick the larger or smaller node value first? Commit to your answer.

Concept: Learn to compare current nodes from both lists to decide which to add next.

At each step, look at the current nodes of both lists. Compare their values. Pick the node with the smaller value to add to the merged list. Move forward in that list to the next node. Repeat until one list ends.

Result

You build a new list in sorted order by always choosing the smaller node.

Understanding this comparison step is key to maintaining sorted order during merge.

4

Intermediate

Handling Remaining Nodes After Merge

🤔Before reading on: After one list ends, do you think you need to compare nodes again or just append the rest? Commit to your answer.

Concept: Learn what to do when one list finishes before the other.

When one list reaches null, the other list may still have nodes left. Since both lists are sorted, you can simply attach the remaining nodes to the merged list without further comparisons.

Result

The merged list includes all nodes from both lists, fully sorted.

Knowing when to stop comparing and just append saves time and keeps the merge efficient.

5

Intermediate

Implementing Merge with a Dummy Node

Concept: Use a dummy node to simplify building the merged list without special cases for the head.

Create a dummy node that acts as the start of the merged list. Use a pointer to track the last node in the merged list. As you pick nodes from input lists, link them after the pointer and move the pointer forward. At the end, return dummy.next as the merged list head.

Result

Code becomes cleaner and easier to manage, avoiding extra checks for the first node.

Using a dummy node is a common pattern that simplifies linked list operations.

6

Advanced

Iterative Merge Algorithm in JavaScript

🤔Before reading on: Do you think the iterative approach uses recursion or loops? Commit to your answer.

Concept: Write a complete JavaScript function to merge two sorted linked lists using iteration.

function mergeTwoLists(l1, l2) { const dummy = { val: 0, next: null }; 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; } // Example usage: // l1: 1 -> 3 -> 5 -> null // l2: 2 -> 4 -> 6 -> null // merged: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Result

The function returns the head of a new sorted linked list combining both inputs.

Seeing the full iterative code helps connect the concepts and shows a practical, efficient solution.

7

Expert

Recursive Merge Approach and Tradeoffs

🤔Before reading on: Do you think recursion is more or less memory efficient than iteration here? Commit to your answer.

Concept: Learn how to merge lists using recursion and understand its pros and cons.

function mergeTwoListsRecursive(l1, l2) { if (l1 === null) return l2; if (l2 === null) return l1; if (l1.val < l2.val) { l1.next = mergeTwoListsRecursive(l1.next, l2); return l1; } else { l2.next = mergeTwoListsRecursive(l1, l2.next); return l2; } } // Recursive calls build the merged list by choosing smaller nodes first. // However, recursion uses call stack memory proportional to list length.

Result

The recursive function returns the merged list head, but may cause stack overflow on very long lists.

Understanding recursion deepens your grasp of the problem and highlights tradeoffs between simplicity and memory use.

Under the Hood

The merge process works by maintaining pointers to the current nodes of both lists. At each step, it compares values and links the smaller node to the merged list. This continues until one list ends, then the rest of the other list is linked. Internally, this manipulates node references without copying data, making it efficient in time and space.

Why designed this way?

This method was designed to merge sorted sequences efficiently without extra sorting. It avoids creating new nodes by reusing existing ones, saving memory. Alternatives like concatenating then sorting are slower. The dummy node pattern simplifies edge cases, making code easier to write and maintain.

┌─────────────┐       ┌─────────────┐
│ List1 Head  │       │ List2 Head  │
│ 1 -> 3 -> 5│       │ 2 -> 4 -> 6 │
└─────┬──────┘       └─────┬──────┘
      │                    │
      ▼                    ▼
  Compare values: 1 < 2 ? Yes
      │                    │
      ▼                    ▼
  Add 1 to merged list
      │
      ▼
  Move List1 pointer to 3
      │
      ▼
  Repeat until one list ends
      │
      ▼
  Append remaining nodes
      │
      ▼
  Merged List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Myth Busters - 3 Common Misconceptions

Quick: After merging, do you think the original lists remain unchanged or are modified? Commit to your answer.

Common Belief: Merging two lists creates a completely new list without changing the original lists.

Reality: The merge reuses nodes from the original lists by changing their next pointers, so the original lists are modified during merge.

Why it matters: Assuming original lists stay intact can cause bugs if you try to use them later, expecting the same structure.

Quick: Do you think you must copy all nodes to merge lists safely? Commit to your answer.

Common Belief: To merge safely, you must create new nodes copying all values from both lists.

Reality: You can merge by rearranging existing node links without copying, which is more efficient.

Why it matters: Copying nodes wastes memory and time, especially for large lists.

Quick: Is recursion always better than iteration for merging lists? Commit to your answer.

Common Belief: Recursion is always simpler and better for merging linked lists.

Reality: Recursion is simpler to write but uses more memory and risks stack overflow on long lists; iteration is safer for production.

Why it matters: Choosing recursion blindly can cause crashes in real systems with large data.

Expert Zone

1

The dummy node technique avoids special cases for the head node, making code cleaner and less error-prone.

2

Merging by re-linking nodes avoids extra memory allocation, which is critical in memory-constrained environments.

3

Recursive merge elegantly expresses the problem but can cause stack overflow; tail recursion optimization is not guaranteed in JavaScript.

When NOT to use

Avoid merging linked lists when the lists are not sorted; instead, consider sorting first or using data structures like heaps or balanced trees for merging unsorted data.

Production Patterns

In production, iterative merge with dummy nodes is preferred for stability and performance. Merging is a core step in merge sort implementations and in streaming data processing where sorted streams combine in real time.

Connections

Merge Sort Algorithm

Merging sorted lists is the key step in merge sort, which sorts data by recursively splitting and merging.

Understanding list merging clarifies how merge sort efficiently sorts large datasets by combining sorted parts.

Priority Queues (Heaps)

Both merging sorted lists and priority queues manage ordered data to efficiently retrieve smallest elements.

Knowing merging helps understand how priority queues merge multiple sorted streams by always picking the smallest next element.

Real-Time Event Scheduling

Merging sorted linked lists is similar to merging event timelines in real-time systems to maintain chronological order.

This connection shows how merging sorted sequences applies beyond data structures, helping manage time-ordered events in operating systems or simulations.

Common Pitfalls

#1 Modifying original lists unintentionally during merge.

Wrong approach:

function mergeTwoLists(l1, l2) {
let merged = null;
if (l1.val < l2.val) {
merged = l1;
l1 = l1.next;
} else {
merged = l2;
l2 = l2.next;
}
// No dummy node or careful pointer tracking
while (l1 !== null && l2 !== null) {
if (l1.val < l2.val) {
merged.next = l1;
l1 = l1.next;
} else {
merged.next = l2;
l2 = l2.next;
}
merged = merged.next;
}
merged.next = l1 !== null ? l1 : l2;
return merged; // returns last node, not head
}

Correct approach:

function mergeTwoLists(l1, l2) {
const dummy = { val: 0, next: null };
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;
}

Root cause:

Not using a dummy node or separate pointer causes loss of the merged list head and modifies original lists incorrectly.

#2 Forgetting to append remaining nodes after one list ends.

Wrong approach:

function mergeTwoLists(l1, l2) {
const dummy = { val: 0, next: null };
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;
}
// Missing: current.next = l1 !== null ? l1 : l2;
return dummy.next;
}

Correct approach:

function mergeTwoLists(l1, l2) {
const dummy = { val: 0, next: null };
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;
}

Root cause:

Not handling the leftover nodes causes loss of data and incomplete merged list.

Key Takeaways

Merging two sorted linked lists means picking the smaller node from the front of each list repeatedly to build a new sorted list.

Using a dummy node simplifies the merge process by avoiding special cases for the first node.

You can merge by rearranging existing nodes without copying, which is efficient in time and memory.

Iterative merge is safer for large lists, while recursive merge is simpler but risks stack overflow.

Understanding merging is essential for algorithms like merge sort and real-time data processing.

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