The Dummy Node Trick That Makes Merging Sorted Linked Lists Trivial

1. Problem Introduction

Problem: Merge two ascending linked lists into a new ascending linked list and return it. The new linked list is formed by splicing together all nodes of the given two linked lists. Input: Two sorted singly linked lists list1, list2 Output: The head node of the merged sorted linked list

Core Difficulties

Linked list nodes can only be traversed in one direction without backtracking, requiring continuous maintenance of the current splicing position;
The two linked lists have inconsistent lengths; after the loop ends, the remaining untraversed nodes need to be spliced;
Edge case handling: one of the linked lists is empty, or both are empty;
Avoid special logic for handling the head node to write concise and unified code.

Optimal Solution

Dummy Node Iteration Method

Time Complexity: O(m+n), where m and n are the lengths of the two linked lists. Each node is traversed only once;
Space Complexity: O(1), only a constant number of pointers are added, no extra arrays/containers;
Core Interview Points: Dummy node, linked list pointer movement logic.

2. Core Algorithm Idea (Dummy Node Concept)

1. Why Use a Dummy Node?

If a dummy node is not used, you need to first determine the minimum of list1[0] and list2[0] as the head of the result list. The subsequent loop logic and the head node judgment logic become disjointed, leading to numerous if branches in the code and poor readability.

The dummy node dummy is an empty node with no business value, always serving as a fixed starting point:

Use pointer cur to point to dummy, all nodes are uniformly attached to cur.next;
During traversal, only compare the current node values of list1 and list2, attaching the smaller node after cur;
After traversal, dummy.next is the real head node of the merged linked list, which can be returned directly without additional head judgment.

2. Complete Process Steps

Create a dummy head node dummy, define a working pointer cur = dummy;
Loop: When both list1 and list2 still have nodes, compare their node values, attach the smaller node to cur.next, and simultaneously move the corresponding linked list pointer and the working pointer cur;
After the loop ends, one of the linked lists must have been fully traversed. Attach the entire remaining linked list directly after cur;
Return dummy.next, discarding the meaningless dummy head node.

3. Your Handwritten Complete Code (Line-by-Line Breakdown)

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function(list1, list2) {
    // 1. Create dummy head node
    const dummy=new ListNode();
    // 2. cur is the working pointer, initially pointing to the dummy head
    let cur=dummy;

    // 3. When both linked lists have nodes, loop to compare and merge
    while(list1&&list2){
        if(list1.val<list2.val){
            cur.next=list1;
            list1=list1.next
            cur=cur.next;
        }else {
            cur.next=list2;
            list2=list2.next;
            cur=cur.next;
        }
    }

    // 4. Traverse and splice remaining nodes of list1
    while(list1!==null){
        cur.next=list1;
        list1=list1.next;
        cur=cur.next;
    }
    // 5. Traverse and splice remaining nodes of list2
    while(list2!=null) {
        cur.next=list2;
        list2=list2.next;
        cur=cur.next;
    }

    // 6. Return the next of the dummy node, which is the real linked list head
    return dummy.next;
};

4. In-Depth Line-by-Line Analysis

1. Dummy Head Node Initialization

const dummy=new ListNode();
let cur=dummy;

dummy: A placeholder node. dummy.val has no practical meaning and will not appear in the final result;
cur: Working cursor pointer, always points to the last node of the merged linked list. All new nodes are attached to cur.next;
Advantage: Unifies the attachment logic for all nodes, eliminating the need to handle the linked list head separately.

2. Core Merge Loop `while(list1&&list2)`

The loop condition list1 && list2 means: Only when both linked lists currently have nodes do we need to compare their sizes.

if(list1.val<list2.val){
    cur.next=list1; // Attach the smaller list1 node after cur
    list1=list1.next; // Move list1 pointer backward for the next round of comparison
    cur=cur.next; // Move working pointer backward to point to the new end of the list
}else {
    cur.next=list2;
    list2=list2.next;
    cur=cur.next;
}

Three fixed steps:

Assign the smaller node to cur.next to complete the attachment;
Move the original linked list pointer list1/list2 one step forward;
Move the working pointer cur synchronously backward, ensuring cur is always at the tail of the linked list.

3. Two While Loops for Splicing Remaining Nodes

while(list1!==null){cur.next=list1;list1=list1.next;cur=cur.next;}
while(list2!=null) {cur.next=list2;list2=list2.next;cur=cur.next;}

When the first layer loop exits, one of list1 or list2 must be null;
The remaining linked list is a complete ordered chain. The code uses a node-by-node traversal and attachment approach, which is logically intuitive and easier for beginners to understand linked list pointer movement;
Supplementary simplified approach: Linked list nodes inherently carry the complete subsequent chain, so they can be attached in one line without a loop: cur.next = list1 || list2, with identical performance and more concise code.

4. Return Result `return dummy.next`

The dummy head node is only a temporary placeholder. dummy.next is the first node with business value in the merged linked list.

5. Comparison of Two Remaining Node Handling Approaches

Approach 1: Your Node-by-Node Traversal (Beginner-Friendly, Code in This Article)

while(list1!==null){
    cur.next=list1;
    list1=list1.next;
    cur=cur.next;
}
while(list2!=null) {
    cur.next=list2;
    list2=list2.next;
    cur=cur.next;
}

✅ Pros: Fully demonstrates the pointer movement process, suitable for beginners learning linked lists and understanding singly linked structures; ❌ Cons: More lines of code, contains repetitive loop logic.

Approach 2: One-Line Direct Attachment (Concise Standard for Interviews)

cur.next = list1 ? list1 : list2;

✅ Pros: Done in one line, no loop, concise and efficient, common in industrial code; 💡 Principle: A linked list node's next carries the entire subsequent chain. You only need to attach the head node, and all following nodes automatically follow.

Concise Complete Code (Recommended for Interviews)

var mergeTwoLists = function(list1, list2) {
    const dummy = new ListNode();
    let cur = dummy;
    while(list1 && list2) {
        if(list1.val < list2.val) {
            cur.next = list1;
            list1 = list1.next;
        } else {
            cur.next = list2;
            list2 = list2.next;
        }
        cur = cur.next;
    }
    // Directly attach the entire remaining linked list
    cur.next = list1 || list2;
    return dummy.next;
};

6. Analysis of Your Code's Strengths and Weaknesses

✅ Code Strengths

Clear Logical Layering: The main loop merges the two linked lists, and two subsequent loops complete the remaining nodes. The flow is clear at a glance;
Standard Pointer Operations: After each node attachment, the list pointer and working pointer cur are moved synchronously, preventing broken chains or infinite loops;
Standard Use of Dummy Head Node: Perfectly avoids special judgment for the head node, a universal template for linked list problems;
No Null Pointer Risk: All loops perform non-null checks, preventing reads of null.val or null.next.

⚠️ Optimizable Points

Remaining linked lists do not need loop traversal; they can be attached in one line to simplify the code;
The cur=cur.next statement is repeated inside the branches and can be extracted outside the if-else to reduce redundant code:

while(list1&&list2){
    if(list1.val<list2.val){
        cur.next=list1;
        list1=list1.next
    }else {
        cur.next=list2;
        list2=list2.next;
    }
    cur=cur.next; // Extracted outside the branch, written only once
}

7. High-Frequency Interview Q&A Summary

Q1: What is the role of the dummy head node? What problems arise if not used?

A: It unifies the node attachment logic for the head, middle, and tail of the linked list. Without a dummy node, extra logic is needed to determine which of the two linked list heads is smaller to serve as the result head, leading to redundant code branches and error-prone edge cases.

Q2: Why is the time complexity O(m+n)?

A: Each node in the two linked lists is only read and attached once, with no repeated traversal. The dummy node only occupies constant space, resulting in O(1) space complexity.

Q3: How to choose between the recursive solution and the iterative (dummy) solution?

A: Recursive code is shorter but involves a call stack, which can overflow for very long linked lists. In interviews, it's better to write the iterative dummy node solution first, as it offers better stability and is more recognized by interviewers.

Q4: Why not splice both linked lists after the loop ends?

A: The termination condition of the while(list1 && list2) loop is that one of the linked lists has been fully traversed. Only one linked list has remaining nodes, so you just need to attach one or the other.

8. Problem-Solving Summary

Merging two sorted linked lists is a must-practice template problem for getting started with singly linked lists. Master two core concepts:

Dummy Node: Solves the special handling problem of the linked list head, applicable to most linked list addition, deletion, and merging problems;
Two-Pointer Synchronous Traversal: Merging two ordered structures is the foundational idea behind merge sort;
Direct Attachment of Remaining Chain: Linked lists are chain-stored structures; there is no need to copy nodes one by one, just attach the entire remaining chain directly.

Your handwritten node-by-node traversal approach is very suitable for beginners to solidify pointer fundamentals. Once proficient, you can switch to the one-line attachment to streamline the code. Both approaches pass all test cases.