Merge Two Sorted Linked Lists in DSA Python - Execution Trace

Concept Flow - Merge Two Sorted Linked Lists

Create dummy node

↓

Set current pointer to dummy

↓

Compare heads of both lists

↓

Smaller node

↓

Move current and chosen list pointer

↓

Repeat until one list is empty

↓

Attach remaining nodes of non-empty list

↓

Return dummy.next as merged list head

We create a dummy node to start the merged list, then repeatedly pick the smaller head node from the two lists, attach it to the merged list, and move pointers until one list is empty. Finally, we attach the leftover nodes.

Execution Sample

DSA Python

def mergeTwoLists(l1, l2):
    dummy = ListNode(0)
    current = dummy
    while l1 and 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 or l2
    return dummy.next

This code merges two sorted linked lists by comparing their nodes and building a new sorted list.

Execution Table

Step	Operation	l1 Node	l2 Node	Current Pointer	Pointer Changes	Merged List Visual
1	Create dummy node and set current	1 -> 3 -> 5 -> null	2 -> 4 -> 6 -> null	dummy(0)	current = dummy	0(dummy) -> null
2	Compare l1.val(1) < l2.val(2)	1 -> 3 -> 5 -> null	2 -> 4 -> 6 -> null	dummy(0)	current.next = l1(1)	0(dummy) -> 1 -> null
3	Move l1 to next (3), current to next (1)	3 -> 5 -> null	2 -> 4 -> 6 -> null	1	l1 = 3, current = 1	0(dummy) -> 1 -> null
4	Compare l1.val(3) < l2.val(2)	3 -> 5 -> null	2 -> 4 -> 6 -> null	1	current.next = l2(2)	0(dummy) -> 1 -> 2 -> null
5	Move l2 to next (4), current to next (2)	3 -> 5 -> null	4 -> 6 -> null	2	l2 = 4, current = 2	0(dummy) -> 1 -> 2 -> null
6	Compare l1.val(3) < l2.val(4)	3 -> 5 -> null	4 -> 6 -> null	2	current.next = l1(3)	0(dummy) -> 1 -> 2 -> 3 -> null
7	Move l1 to next (5), current to next (3)	5 -> null	4 -> 6 -> null	3	l1 = 5, current = 3	0(dummy) -> 1 -> 2 -> 3 -> null
8	Compare l1.val(5) < l2.val(4)	5 -> null	4 -> 6 -> null	3	current.next = l2(4)	0(dummy) -> 1 -> 2 -> 3 -> 4 -> null
9	Move l2 to next (6), current to next (4)	5 -> null	6 -> null	4	l2 = 6, current = 4	0(dummy) -> 1 -> 2 -> 3 -> 4 -> null
10	Compare l1.val(5) < l2.val(6)	5 -> null	6 -> null	4	current.next = l1(5)	0(dummy) -> 1 -> 2 -> 3 -> 4 -> 5 -> null
11	Move l1 to next (null), current to next (5)	null	6 -> null	5	l1 = null, current = 5	0(dummy) -> 1 -> 2 -> 3 -> 4 -> 5 -> null
12	l1 is empty, attach remaining l2	null	6 -> null	5	current.next = l2(6)	0(dummy) -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
13	Return dummy.next as merged list head	null	6 -> null	5	return dummy.next	1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

💡 Loop ends when l1 is empty at step 11, remaining l2 nodes attached at step 12

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	Final
l1	1 -> 3 -> 5 -> null	3 -> 5 -> null	3 -> 5 -> null	5 -> null	5 -> null	null	null	null	null	null	null	null	null
l2	2 -> 4 -> 6 -> null	2 -> 4 -> 6 -> null	4 -> 6 -> null	4 -> 6 -> null	6 -> null	6 -> null	6 -> null	6 -> null	6 -> null	6 -> null	6 -> null	6 -> null	6 -> null
current	dummy(0)	1	2	3	4	5	5	5	5	5	5	5	5

Key Moments - 3 Insights

Why do we use a dummy node instead of starting directly with l1 or l2?

The dummy node simplifies the code by providing a fixed starting point for the merged list. Without it, we would need extra checks to set the head of the merged list. See execution_table step 1 where dummy is created and current points to it.

Why do we attach the remaining nodes after one list is empty?

Because both lists are sorted, the remaining nodes in the non-empty list are already in order and can be attached directly. This happens at step 12 in the execution_table.

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

Moving current ensures that the next attached node is linked correctly after the last node in the merged list. This is shown in steps 3, 5, 7, 9, and 11 where current moves forward.

Visual Quiz - 3 Questions

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

A Node with value 4 from l2

B Node with value 3 from l1

C Node with value 2 from l2

D Node with value 5 from l1

💡 Hint

Check the 'Pointer Changes' and 'Merged List Visual' columns at step 6 in execution_table

At which step does l1 become empty?

A Step 11

B Step 10

C Step 12

D Step 13

💡 Hint

Look at the 'l1 Node' column in execution_table and variable_tracker to see when it becomes null

If l1 started with values all greater than l2, how would the merged list start?

A With nodes from l1 first

B Alternating nodes from l1 and l2

C With nodes from l2 first

D Empty list

💡 Hint

Since we always attach the smaller node first, check the comparison logic in concept_flow and execution_table

Concept Snapshot

Merge Two Sorted Linked Lists:
- Use a dummy node to start merged list
- Compare heads of both lists
- Attach smaller node to merged list
- Move pointers forward
- Repeat until one list is empty
- Attach remaining nodes
- Return dummy.next as head

Full Transcript

To merge two sorted linked lists, we start by creating a dummy node to simplify list construction. We use a current pointer starting at dummy. We compare the values at the heads of both lists and attach the smaller node to current.next. Then we move current and the chosen list's pointer forward. We repeat this until one list is empty. Finally, we attach the remaining nodes of the non-empty list to current.next. We return dummy.next as the head of the merged sorted list. This approach ensures the merged list is sorted without extra sorting steps.

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 the order of elements in both lists

C. To find the largest element in both lists

D. To delete duplicate elements from both lists

Solution

1. Step 1: Understand the merging process

   Merging two sorted linked lists means combining them into one list that keeps the sorted order.

2. Step 2: Identify the goal

   The goal is to have a new linked list that contains all elements from both lists in sorted order.

3. Final Answer:

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

4. Quick Check:

   Merging = combine sorted lists [OK]

Hint: Merging keeps order and combines all elements [OK]

Common Mistakes:

• Thinking merging reverses lists
• Only finding largest element
• Removing duplicates instead of merging

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

easy

A. def mergeLists(l1, l2):
current = ListNode(0)
dummy = current.next

B. def mergeLists(l1, l2):
dummy = null
current = dummy

C. def mergeLists(l1, l2):
dummy = ListNode(0)
current = dummy

D. def mergeLists(l1, l2):
dummy = ListNode(0)
current = dummy.next

Solution

1. Step 1: Initialize dummy and current nodes properly

   We create a dummy node with value 0 and set current to dummy to build the merged list.

2. Step 2: Check options for correct syntax

   def mergeLists(l1, l2): dummy = ListNode(0) current = dummy correctly creates dummy and current pointing to dummy. def mergeLists(l1, l2): dummy = ListNode(0) current = dummy.next incorrectly sets current = dummy.next which is initially None.

3. Final Answer:

   def mergeLists(l1, l2): dummy = ListNode(0) current = dummy -> Option C

4. Quick Check:

   Dummy node with value 0 starts merge [OK]

Hint: Start with dummy node value 0 and current pointing to dummy [OK]

Common Mistakes:

• Setting current to dummy.next
• Swapping dummy and current incorrectly
• Setting dummy to null

3. What will be the output linked list after merging these two sorted lists? List 1: 1 -> 3 -> 5 -> null List 2: 2 -> 4 -> 6 -> null Use the merge logic to combine them.

medium

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

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

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

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

Solution

1. Step 1: Compare nodes from both lists in order

   Start with 1 (List 1) and 2 (List 2). 1 is smaller, add 1. Then compare 3 and 2, add 2. Continue comparing and adding smaller nodes.

2. Step 2: Build merged list step-by-step

   Merged list becomes 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null after adding all nodes in sorted order.

3. Final Answer:

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

4. Quick Check:

   Sorted merge combines nodes in ascending order [OK]

Hint: Pick smaller node each step to keep order [OK]

Common Mistakes:

• Appending one list fully before the other
• Mixing node order incorrectly
• Skipping nodes during merge

4. Identify the error in this merge function snippet:

def mergeLists(l1, l2):
    dummy = ListNode(0)
    current = dummy
    while l1 and l2:
        if l1.val < l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
    current.next = l1 if l1 else l2
    return dummy.next

medium

A. The 'current' pointer is not moved forward inside the loop

B. The dummy node is not initialized correctly

C. The function does not handle empty input lists

D. The return statement should return 'current' instead of 'dummy.next'

Solution

1. Step 1: Check pointer updates inside the loop

   After assigning current.next, the current pointer must move forward to current.next to continue building the list.

2. Step 2: Identify missing current update

   The code misses 'current = current.next' inside the while loop, causing an infinite loop or incorrect list.

3. Final Answer:

   The 'current' pointer is not moved forward inside the loop -> Option A

4. Quick Check:

   Move current forward after linking nodes [OK]

Hint: Always move current pointer after linking a node [OK]

Common Mistakes:

• Forgetting to move current pointer
• Returning wrong node
• Not handling empty lists (though not error here)

5. Given two sorted linked lists where one list is empty and the other is 0 -> 2 -> 4 -> null, what should the merged list be?

medium

A. 0 -> null

B. null

C. 4 -> 2 -> 0 -> null

D. 0 -> 2 -> 4 -> null

Solution

1. Step 1: Understand merging with an empty list

   If one list is empty, the merged list is just the non-empty list as it is already sorted.

2. Step 2: Apply to given lists

   Since the second list is empty and the first is 0 -> 2 -> 4 -> null, the merged list remains 0 -> 2 -> 4 -> null.

3. Final Answer:

   0 -> 2 -> 4 -> null -> Option D

4. Quick Check:

   Merging with empty list returns the other list [OK]

Hint: Empty list merge returns the other list unchanged [OK]

Common Mistakes:

• Returning null when one list is empty
• Reversing the non-empty list
• Returning only the first node