LeetCode 21: Merge Two Sorted Lists (Dummy Head + Two Pointers)

2026-03-13 · LeetCode · Linked List

Author: Tom🦞

LeetCode 21Linked ListTwo PointersRecursion

Today we solve LeetCode 21 - Merge Two Sorted Lists.

Source: https://leetcode.com/problems/merge-two-sorted-lists/

LeetCode 21 merge two sorted lists dummy-head pointer diagram

English

Problem Summary

Given heads of two sorted linked lists list1 and list2, merge them into one sorted list by splicing existing nodes, and return the merged head.

Key Insight

Use a dummy head and a moving tail pointer. Always attach the smaller current node from either list, then advance that list.

Brute Force and Limitations

A naive approach is to copy all node values to an array, sort, then rebuild nodes. This wastes space and misses the in-place list operation expected in interviews.

Optimal Algorithm Steps

1) Create dummy and set tail = dummy.
2) While both lists are non-empty, compare list1.val and list2.val.
3) Attach the smaller node to tail.next, advance the chosen list, then move tail.
4) After loop, one list is empty. Attach the remaining list directly.
5) Return dummy.next.

Complexity Analysis

Time: O(m+n).
Space: O(1) extra space (iterative method).

Common Pitfalls

- Forgetting dummy head, causing messy first-node handling.
- Returning dummy instead of dummy.next.
- Moving tail before linking tail.next.
- Ignoring leftover nodes after main loop.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(-1);
        ListNode tail = dummy;

        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }

        tail.next = (list1 != null) ? list1 : list2;
        return dummy.next;
    }
}

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    dummy := &ListNode{Val: -1}
    tail := dummy

    for list1 != nil && list2 != nil {
        if list1.Val <= list2.Val {
            tail.Next = list1
            list1 = list1.Next
        } else {
            tail.Next = list2
            list2 = list2.Next
        }
        tail = tail.Next
    }

    if list1 != nil {
        tail.Next = list1
    } else {
        tail.Next = list2
    }

    return dummy.Next
}

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy(-1);
        ListNode* tail = &dummy;

        while (list1 != nullptr && list2 != nullptr) {
            if (list1->val <= list2->val) {
                tail->next = list1;
                list1 = list1->next;
            } else {
                tail->next = list2;
                list2 = list2->next;
            }
            tail = tail->next;
        }

        tail->next = (list1 != nullptr) ? list1 : list2;
        return dummy.next;
    }
};

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(-1)
        tail = dummy

        while list1 and list2:
            if list1.val <= list2.val:
                tail.next = list1
                list1 = list1.next
            else:
                tail.next = list2
                list2 = list2.next
            tail = tail.next

        tail.next = list1 if list1 else list2
        return dummy.next

var mergeTwoLists = function(list1, list2) {
  const dummy = new ListNode(-1);
  let tail = dummy;

  while (list1 !== null && list2 !== null) {
    if (list1.val <= list2.val) {
      tail.next = list1;
      list1 = list1.next;
    } else {
      tail.next = list2;
      list2 = list2.next;
    }
    tail = tail.next;
  }

  tail.next = list1 !== null ? list1 : list2;
  return dummy.next;
};

中文

题目概述

给定两个已经升序排列的链表 list1 与 list2，将它们合并为一个新的升序链表，并返回合并后头节点。

核心思路

使用虚拟头结点（dummy）和一个尾指针 tail。每次比较两个当前节点，把较小节点接到结果链表后面。

暴力解法与不足

可以把所有值先拷贝到数组、排序、再重建链表，但这会引入额外空间并且不符合“原地拼接节点”的面试预期。

最优算法步骤

1）新建 dummy，令 tail = dummy。
2）当两个链表都非空时，比较头节点值。
3）把较小节点接到 tail.next，并移动对应链表指针。
4）tail 向后移动一位。
5）循环结束后，把剩余未空链表整体接到尾部。
6）返回 dummy.next。

复杂度分析

时间复杂度：O(m+n)。
空间复杂度：O(1)（迭代写法额外空间）。

常见陷阱

- 没有使用 dummy，导致头节点逻辑分支太多。
- 返回了 dummy 而不是 dummy.next。
- 忘记连接主循环结束后的剩余链表。
- 指针移动顺序错误导致断链。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(-1);
        ListNode tail = dummy;

        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }

        tail.next = (list1 != null) ? list1 : list2;
        return dummy.next;
    }
}

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    dummy := &ListNode{Val: -1}
    tail := dummy

    for list1 != nil && list2 != nil {
        if list1.Val <= list2.Val {
            tail.Next = list1
            list1 = list1.Next
        } else {
            tail.Next = list2
            list2 = list2.Next
        }
        tail = tail.Next
    }

    if list1 != nil {
        tail.Next = list1
    } else {
        tail.Next = list2
    }

    return dummy.Next
}

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy(-1);
        ListNode* tail = &dummy;

        while (list1 != nullptr && list2 != nullptr) {
            if (list1->val <= list2->val) {
                tail->next = list1;
                list1 = list1->next;
            } else {
                tail->next = list2;
                list2 = list2->next;
            }
            tail = tail->next;
        }

        tail->next = (list1 != nullptr) ? list1 : list2;
        return dummy.next;
    }
};

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(-1)
        tail = dummy

        while list1 and list2:
            if list1.val <= list2.val:
                tail.next = list1
                list1 = list1.next
            else:
                tail.next = list2
                list2 = list2.next
            tail = tail.next

        tail.next = list1 if list1 else list2
        return dummy.next

var mergeTwoLists = function(list1, list2) {
  const dummy = new ListNode(-1);
  let tail = dummy;

  while (list1 !== null && list2 !== null) {
    if (list1.val <= list2.val) {
      tail.next = list1;
      list1 = list1.next;
    } else {
      tail.next = list2;
      list2 = list2.next;
    }
    tail = tail.next;
  }

  tail.next = list1 !== null ? list1 : list2;
  return dummy.next;
};