Merge Two Sorted Linked Lists in DSA Java - Execution Trace

Concept Flow - Merge Two Sorted Linked Lists

Start with two sorted lists

↓

Compare head nodes of both lists

↓

Add smaller node to merged list

↓

Move pointer in list of smaller node

↓

Repeat comparison until one list ends

↓

Attach remaining nodes of non-empty list

↓

Merged list ready

Start with two sorted lists, repeatedly pick the smaller head node to add to the merged list, move pointers accordingly, and finally attach any leftover nodes.

Execution Sample

DSA Java

ListNode merge(ListNode l1, ListNode l2) {
  ListNode dummy = new ListNode(0);
  ListNode 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;
}

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	Initialize dummy and current pointers	l1: 1 -> 3 -> 5 -> null, l2: 2 -> 4 -> 6 -> null	dummy -> 0, current -> dummy	dummy(0) -> null l1: 1 -> 3 -> 5 l2: 2 -> 4 -> 6
2	Compare l1.val=1 and l2.val=2; 1 <= 2	Same as above	current.next = l1(1), l1 moves to 3	dummy(0) -> 1 -> null l1: 3 -> 5 l2: 2 -> 4 -> 6
3	Move current to current.next (1)	Same as above	current -> 1	dummy(0) -> 1 current at 1 l1: 3 -> 5 l2: 2 -> 4 -> 6
4	Compare l1.val=3 and l2.val=2; 3 > 2	Same as above	current.next = l2(2), l2 moves to 4	dummy(0) -> 1 -> 2 -> null l1: 3 -> 5 l2: 4 -> 6
5	Move current to current.next (2)	Same as above	current -> 2	dummy(0) -> 1 -> 2 current at 2 l1: 3 -> 5 l2: 4 -> 6
6	Compare l1.val=3 and l2.val=4; 3 <= 4	Same as above	current.next = l1(3), l1 moves to 5	dummy(0) -> 1 -> 2 -> 3 -> null l1: 5 l2: 4 -> 6
7	Move current to current.next (3)	Same as above	current -> 3	dummy(0) -> 1 -> 2 -> 3 current at 3 l1: 5 l2: 4 -> 6
8	Compare l1.val=5 and l2.val=4; 5 > 4	Same as above	current.next = l2(4), l2 moves to 6	dummy(0) -> 1 -> 2 -> 3 -> 4 -> null l1: 5 l2: 6
9	Move current to current.next (4)	Same as above	current -> 4	dummy(0) -> 1 -> 2 -> 3 -> 4 current at 4 l1: 5 l2: 6
10	Compare l1.val=5 and l2.val=6; 5 <= 6	Same as above	current.next = l1(5), l1 moves to null	dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> null l1: null l2: 6
11	Move current to current.next (5)	Same as above	current -> 5	dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5 current at 5 l1: null l2: 6
12	l1 is null, attach remaining l2 nodes	Same as above	current.next = l2(6)	dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null l1: null l2: 6
13	Return merged list starting at dummy.next	Merged list: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null	No pointer changes	Merged list: 1 -> 2 -> 3 -> 4 -> 5 -> 6
14	Exit	All nodes merged	No pointer changes	Merged list complete

💡 Both lists fully merged; no nodes left to process

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	After 10	After 11	After 12	Final
l1	1 -> 3 -> 5	3 -> 5	3 -> 5	3 -> 5	3 -> 5	5	5	5	5	null	null	null	null	null
l2	2 -> 4 -> 6	2 -> 4 -> 6	2 -> 4 -> 6	4 -> 6	4 -> 6	4 -> 6	4 -> 6	6	6	6	6	6	6	6
current	dummy(0)	dummy(0)	1	1	2	2	3	3	4	4	5	5	5	5
merged list	empty	0 -> 1	0 -> 1	0 -> 1 -> 2	0 -> 1 -> 2	0 -> 1 -> 2 -> 3	0 -> 1 -> 2 -> 3	0 -> 1 -> 2 -> 3 -> 4	0 -> 1 -> 2 -> 3 -> 4	0 -> 1 -> 2 -> 3 -> 4 -> 5	0 -> 1 -> 2 -> 3 -> 4 -> 5	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6	1 -> 2 -> 3 -> 4 -> 5 -> 6

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 execution_table step 1 where dummy is initialized and used as a stable start.

Why do we move the 'current' pointer after linking a node?

Moving 'current' ensures the next node is linked after the last node added. See steps 3, 5, 7, 9, 11 where current moves forward to keep track of the merged list's end.

What happens when one list becomes empty before the other?

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

Visual Quiz - 3 Questions

Look at the execution_table at step 6, which node is linked to the merged list?

A Node with value 2 from l2

B Node with value 3 from l1

C Node with value 4 from l2

D Node with value 1 from l1

💡 Hint

Check the 'Operation' and 'Pointer Changes' columns at step 6 in execution_table.

At which step does the pointer 'l1' become null?

A Step 10

B Step 11

C Step 9

D Step 12

💡 Hint

Look at the 'l1' values in variable_tracker after each step.

If the first node of l2 was smaller than l1's first node, how would step 2 change?

A No change, current.next links to dummy

B current.next would link to l1's first node

C current.next would link to l2's first node

D Both l1 and l2 pointers move forward

💡 Hint

Refer to the comparison logic in execution_table step 2.

Concept Snapshot

Merge Two Sorted Linked Lists:
- Use a dummy node to start merged list
- Compare heads of both lists
- Link smaller node to merged list
- Move pointer in chosen list and current
- Repeat until one list ends
- Attach remaining nodes of other list
- Return dummy.next as merged head

Full Transcript

This visualization shows how to merge two sorted linked lists step-by-step. We start with two lists and a dummy node to simplify linking. At each step, we compare the current nodes of both lists, link the smaller one to the merged list, and move pointers forward. When one list ends, we attach the remaining nodes of the other list. The dummy node's next pointer points to the head of the merged sorted list. Variables like l1, l2, current, and the merged list state are tracked after each operation to clearly show how the lists combine into one sorted list.

Practice

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

easy

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

B. To reverse both linked lists

C. To find the maximum element in both lists

D. To delete duplicate elements from both lists

Solution

1. Step 1: Understand the input lists

   Two linked lists are sorted individually, meaning their elements are in ascending order.

2. Step 2: Merge while maintaining order

   The goal is to combine these two lists into one sorted list that contains all elements from both.

3. Final Answer:

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

4. Quick Check:

   Merging sorted lists means combining all elements in order [OK]

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

Common Mistakes:

• Thinking merge means reversing lists
• Assuming merge removes duplicates
• Confusing merge with finding max element

2. Which of the following Java method signatures correctly represents a function to merge two sorted linked lists of integers?

easy

A. public int merge(ListNode l1, ListNode l2)

B. public void merge(int l1, int l2)

C. public ListNode merge(ListNode l1, ListNode l2)

D. public ListNode merge(int[] l1, int[] l2)

Solution

1. Step 1: Identify correct parameter types

   The function should accept two linked lists, so parameters must be ListNode types, not primitives or arrays.

2. Step 2: Identify correct return type

   The function returns a merged linked list, so return type should be ListNode, not void or int.

3. Final Answer:

   public ListNode merge(ListNode l1, ListNode l2) -> Option C

4. Quick Check:

   Method with ListNode params and return type is correct [OK]

Hint: Method merges two ListNode inputs and returns ListNode [OK]

Common Mistakes:

• Using primitive types instead of ListNode
• Returning void instead of ListNode
• Using arrays instead of linked lists

3. What is the output linked list after merging these two sorted lists?

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

medium

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

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

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

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

Solution

1. Step 1: Compare first nodes of both lists

   1 (List 1) is less than 2 (List 2), so 1 is first in merged list.

2. Step 2: Continue comparing next nodes

   Next compare 3 and 2, 2 is smaller, add 2, then 3 vs 4, add 3, then 5 vs 4, add 4, then 5 vs 6, add 5, finally add 6.

3. Final Answer:

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

4. Quick Check:

   Merge keeps ascending order combining both lists [OK]

Hint: Pick smaller head node repeatedly to merge sorted lists [OK]

Common Mistakes:

• Appending one list after the other without sorting
• Reversing order of merged list
• Skipping nodes during merge

4. Given the following code snippet to merge two sorted linked lists, what is the error?

public ListNode merge(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;
    if (l1.val < l2.val) {
        l1.next = merge(l1.next, l2);
        return l1;
    } else {
        l2.next = merge(l1, l2.next);
        return l2;
    }
}

medium

A. Missing base case for both lists being null

B. No error; code correctly merges two sorted linked lists

C. Incorrect comparison operator; should be <= instead of <

D. Function does not handle empty lists properly

Solution

1. Step 1: Check base cases

   Code returns the other list if one is null, correctly handling empty lists.

2. Step 2: Check recursive merge logic

   Compares values, recursively merges next nodes, and returns the smaller node, which is correct.

3. Final Answer:

   No error; code correctly merges two sorted linked lists -> Option B

4. Quick Check:

   Recursive merge with base cases is correct [OK]

Hint: Check base cases and recursive calls carefully [OK]

Common Mistakes:

• Forgetting to return merged list
• Incorrect base case handling
• Wrong comparison operator causing order issues

5. You have two sorted linked lists:

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

After merging, what is the correct merged list?
Also, explain why the merged list contains duplicate values.

hard

A. 1 -> 1 -> 3 -> 4 -> 4 -> 5 -> null

B. 1 -> 3 -> 4 -> 5 -> null

C. 1 -> 4 -> 5 -> 3 -> null

D. 1 -> 1 -> 4 -> 5 -> null

Solution

1. Step 1: Merge nodes in ascending order

   Compare heads: both 1, add both 1s. Then 4 vs 3, add 3. Then 4 vs 4, add both 4s. Finally add 5.

2. Step 2: Understand duplicates in merged list

   Duplicates appear because both lists contain the same values independently; merge keeps all elements without removing duplicates.

3. Final Answer:

   1 -> 1 -> 3 -> 4 -> 4 -> 5 -> null -> Option A

4. Quick Check:

   Merge keeps all elements including duplicates [OK]

Hint: Merge keeps duplicates if present in input lists [OK]

Common Mistakes:

• Removing duplicates during merge
• Appending lists without sorting
• Skipping nodes with same values