Merge Two Sorted Linked Lists in DSA Javascript - Execution Trace

Concept Flow - Merge Two Sorted Linked Lists

Create dummy node

↓

Set current pointer to dummy

↓

While both lists not empty

↓

Compare list1.val and list2.val

↓

Attach smaller node to current.next

↓

Move current and chosen list pointer forward

↓

Attach remaining nodes of non-empty list

↓

Return dummy.next as merged list head

Start with a dummy node and a pointer. Compare nodes from both lists, attach the smaller to the merged list, move pointers forward. When one list ends, attach the rest of the other list.

Execution Sample

DSA Javascript

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

Merges two sorted linked lists by comparing nodes and linking the smaller one to the merged list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create dummy node and set current to dummy	dummy(0) -> null	current = dummy	dummy(0) -> null
2	Compare l1.val=1 and l2.val=1	l1:1->2->4, l2:1->3->4	current.next = l1, l1 = l1.next (2)	dummy(0) -> 1 -> null
3	Move current to current.next (1)	dummy(0) -> 1 -> null	current = current.next (1)	dummy(0) -> 1 -> null
4	Compare l1.val=2 and l2.val=1	l1:2->4, l2:1->3->4	current.next = l2, l2 = l2.next (3)	dummy(0) -> 1 -> 1 -> null
5	Move current to current.next (1)	dummy(0) -> 1 -> 1 -> null	current = current.next (1)	dummy(0) -> 1 -> 1 -> null
6	Compare l1.val=2 and l2.val=3	l1:2->4, l2:3->4	current.next = l1, l1 = l1.next (4)	dummy(0) -> 1 -> 1 -> 2 -> null
7	Move current to current.next (2)	dummy(0) -> 1 -> 1 -> 2 -> null	current = current.next (2)	dummy(0) -> 1 -> 1 -> 2 -> null
8	Compare l1.val=4 and l2.val=3	l1:4, l2:3->4	current.next = l2, l2 = l2.next (4)	dummy(0) -> 1 -> 1 -> 2 -> 3 -> null
9	Move current to current.next (3)	dummy(0) -> 1 -> 1 -> 2 -> 3 -> null	current = current.next (3)	dummy(0) -> 1 -> 1 -> 2 -> 3 -> null
10	Compare l1.val=4 and l2.val=4	l1:4, l2:4	current.next = l1, l1 = l1.next (null)	dummy(0) -> 1 -> 1 -> 2 -> 3 -> 4 -> null
11	Move current to current.next (4)	dummy(0) -> 1 -> 1 -> 2 -> 3 -> 4 -> null	current = current.next (4)	dummy(0) -> 1 -> 1 -> 2 -> 3 -> 4 -> null
12	l1 is null, attach remaining l2 (4)	l2:4	current.next = l2	dummy(0) -> 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> null
13	Return merged list starting at dummy.next	Merged list: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> null	No pointer changes	1 -> 1 -> 2 -> 3 -> 4 -> 4 -> null

💡 Loop ends when one list is empty; remaining nodes attached to merged list.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	After Step 10	After Step 12	Final
l1	1->2->4	2->4	2->4	4	4	null	null	null
l2	1->3->4	1->3->4	3->4	3->4	4	4	null	null
current	dummy(0)	dummy(0)->1	dummy(0)->1->1	dummy(0)->1->1->2	dummy(0)->1->1->2->3	dummy(0)->1->1->2->3->4	dummy(0)->1->1->2->3->4->4	dummy(0)->1->1->2->3->4->4

Key Moments - 3 Insights

Why do we use a dummy node at the start?

The dummy node simplifies linking nodes without checking if the merged list is empty. See steps 1 and 2 in execution_table where dummy is created and current points to it.

Why do we move the current pointer after attaching a node?

Moving current ensures the next attached node links correctly after the last node. See steps 3, 5, 7, 9, and 11 where current moves forward after attaching nodes.

What happens when one list becomes empty before the other?

When one list is empty, we attach the remaining nodes of the other list directly. See step 12 where l1 is null and remaining l2 nodes are attached.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the value of l1?

A 4

B 2 -> 4

C null

D 1 -> 2 -> 4

💡 Hint

Check the 'Pointer Changes' and 'Nodes in List' columns at step 6.

At which step does the loop end because one list becomes empty?

A Step 10

B Step 13

C Step 12

D Step 8

💡 Hint

Look for the step where 'l1 is null' and remaining nodes are attached.

If we changed the comparison to 'l1.val < l2.val' instead of '<=', what would happen at step 2?

A l2 node would be attached instead of l1

B l1 node would be attached as before

C Both nodes would be attached simultaneously

D The loop would terminate early

💡 Hint

Check the comparison result at step 2 and which node is attached.

Concept Snapshot

Merge Two Sorted Linked Lists:
- Use a dummy node to start merged list.
- Compare nodes from both lists.
- Attach smaller node to merged list.
- Move pointers forward.
- Attach remaining nodes when one list ends.
- Return dummy.next as merged list head.

Full Transcript

This visualization shows how to merge two sorted linked lists step-by-step. We start by creating a dummy node and a current pointer. Then, while both lists have nodes, we compare their current values. We attach the smaller node to the merged list and move the pointers forward. When one list runs out of nodes, we attach the remaining nodes of the other list. Finally, we return the merged list starting from dummy.next. The execution table tracks each step, showing pointer changes and the visual state of the merged list. Key moments clarify why we use a dummy node, why we move the current pointer, and what happens when one list is empty. The quiz tests understanding of pointer values and loop termination.

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