Merge Two Sorted Linked Lists: Two Pointers and a Dummy Node

Table of Contents

Problem Description Solution Approach Core Idea: Two Pointers Comparing One by One The Role of the Dummy Node Algorithm Steps Code Implementation Illustrated Process Complexity Analysis Key Points Extended Thinking

814 words

4 minutes

Merge Two Sorted Linked Lists: Two Pointers and a Dummy Node

2026-08-10

Algorithms

Linked List

/

Two Pointers

/

Merge

/

C

/

C++

/

JavaScript

Problem Description#

Merge two ascending linked lists list1 and list2 into a new ascending linked list, and return the head node of the merged linked list. The new linked list is formed by concatenating all the nodes of the two input linked lists.

1
Input: list1 = 1→2→4, list2 = 1→3→4
2
Output: 1→1→2→3→4→4

Solution Approach#

Core Idea: Two Pointers Comparing One by One#

Imagine you have two stacks of playing cards sorted from smallest to largest, and you want to merge them into one stack. Each time, you only need to look at the top card of each stack and take the smaller one and put it into the result.

For linked lists, this process of “compare → take the smaller one → advance the pointer” can be perfectly implemented with two pointers.

The Role of the Dummy Node#

Who is the first node of the merged linked list? Is it the head of list1 or the head of list2? This judgment would make the code verbose. Introduce a dummy head node (dummy), append all nodes uniformly after the dummy, and finally return dummy.next.

Algorithm Steps#

Create a dummy node and a tail pointer tail
Traverse both linked lists simultaneously, comparing the current node values
Attach the smaller node after tail, and advance the corresponding pointer
When either linked list is fully traversed, directly attach the remaining linked list to the tail
Return dummy.next

Code Implementation#

1
#include <stdio.h>
2
#include <stdlib.h>
3

4
typedef struct ListNode {
5
    int val;
6
    struct ListNode *next;
7
} ListNode;
8

9
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
10
    // Create a dummy virtual head node
11
    ListNode dummy;
12
    dummy.next = NULL;
13
    ListNode* tail = &dummy;
14

15
    // Traverse both linked lists with two pointers
16
    while (list1 && list2) {
17
        if (list1->val <= list2->val) {
18
            tail->next = list1;
19
            list1 = list1->next;
20
        } else {
21
            tail->next = list2;
22
            list2 = list2->next;
23
        }
24
        tail = tail->next;
25
    }
26

27
    // Attach the remaining linked list to the tail
28
    tail->next = list1 ? list1 : list2;
29

30
    return dummy.next;
31
}

1
struct ListNode {
2
    int val;
3
    ListNode *next;
4
    ListNode() : val(0), next(nullptr) {}
5
    ListNode(int x) : val(x), next(nullptr) {}
6
    ListNode(int x, ListNode *next) : val(x), next(next) {}
7
};
8

9
class Solution {
10
public:
11
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
12
        // Create a dummy virtual head node
13
        ListNode dummy(0);
14
        ListNode* tail = &dummy;
15

16
        // Traverse both linked lists with two pointers
17
        while (list1 && list2) {
18
            if (list1->val <= list2->val) {
19
                tail->next = list1;
20
                list1 = list1->next;
21
            } else {
22
                tail->next = list2;
23
                list2 = list2->next;
24
            }
25
            tail = tail->next;
26
        }
27

28
        // Attach the remaining linked list to the tail
29
        tail->next = list1 ? list1 : list2;
30

31
        return dummy.next;
32
    }
33
};

1
class ListNode {
2
    constructor(val, next) {
3
        this.val = (val === undefined ? 0 : val);
4
        this.next = (next === undefined ? null : next);
5
    }
6
}
7

8
function mergeTwoLists(list1, list2) {
9
    // Create a dummy virtual head node
10
    const dummy = new ListNode(0);
11
    let tail = dummy;
12

13
    // Traverse both linked lists with two pointers
14
    while (list1 && list2) {
15
        if (list1.val <= list2.val) {
16
            tail.next = list1;
17
            list1 = list1.next;
18
        } else {
19
            tail.next = list2;
20
            list2 = list2.next;
21
        }
22
        tail = tail.next;
23
    }
24

25
    // Attach the remaining linked list to the tail
26
    tail.next = list1 ? list1 : list2;
27

28
    return dummy.next;
29
}

Illustrated Process#

1
Initial state:
2
list1:  1 → 2 → 4
3
list2:  1 → 3 → 4
4
dummy: [ ] → ?
5

6
Step 1: Compare 1 and 1 → take 1 from list1
7
dummy → 1(list1)  tail=1
8

9
Step 2: Compare 2 and 1 → take 1 from list2
10
dummy → 1 → 1(list2)  tail=1(list2)
11

12
Step 3: Compare 2 and 3 → take 2 from list1
13
dummy → 1 → 1 → 2(list1)  tail=2
14

15
Step 4: Compare 4 and 3 → take 3 from list2
16
dummy → 1 → 1 → 2 → 3(list2)  tail=3
17

18
Step 5: Compare 4 and 4 → take 4 from list1
19
dummy → 1 → 1 → 2 → 3 → 4(list1)  tail=4
20

21
Step 6: list1 is empty, append the remaining part of list2
22
dummy → 1 → 1 → 2 → 3 → 4 → 4(list2)
23

24
Result: 1→1→2→3→4→4

Complexity Analysis#

Dimension	Analysis
Time Complexity	O(m + n) — Each linked list is traversed once
Space Complexity	O(1) — Only two extra pointers, dummy and tail, are used, merging in place

Key Points#

The clever use of the Dummy node: It avoids the special judgment of “who is the head node” and allows all nodes to be handled uniformly
Tail pointer tail: Always points to the last node of the result linked list, making it convenient to append O(1)
Directly concatenating the remaining linked list: After the loop ends, the untraversed linked list is itself ordered, so it can be attached directly

Extended Thinking#

If deduplication is required (keeping only one copy of equal elements), how should it be modified?
If it is required to not allocate new nodes but return a completely new linked list (deep-copying nodes), how should it be handled?