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.