💬 Discord
Sign In
NeetCode #304LC-21EasyLinked ListBlind 75NC 150NC 250
← Back to All Problems

#304 · #21 · Merge Two Sorted Lists(合并两个有序链表)

📌 Problem Statement & Constraints

You are given the heads of two sorted linked lists list1 and list2. Merge them into one sorted list by splicing together the existing nodes. Return the head of the merged list. Constraints: the number of nodes in each list is in [0, 50].

💡 Core Algorithmic Approaches

  1. Use a dummy head to avoid special-casing the first node.
  2. Repeatedly attach the smaller of the two current nodes and advance that pointer.
  3. When one list is exhausted, attach the remainder of the other directly -- no further comparisons are needed.
  4. This is the merge step of merge sort, adapted to linked nodes.

💻 Benchmark Python3 Implementation

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = tail = ListNode(0)
        while list1 and list2:
            if list1.val <= list2.val:      # '<=' keeps the merge stable
                tail.next = list1
                list1 = list1.next
            else:
                tail.next = list2
                list2 = list2.next
            tail = tail.next
        tail.next = list1 or list2          # attach the remainder
        return dummy.next

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m + n): each node is linked once.
💾 Space Complexity
O(1): the nodes are relinked, not copied. A recursive version would use O(m + n) stack space.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the dummy head: the first node would need a separate branch.
  • Looping until both lists are exhausted: after one is empty, the remainder can be attached wholesale.
  • Copying values into new nodes: the problem asks for splicing the existing nodes.
  • Using < instead of <=: still correct, but it makes the merge unstable; <= is the conventional choice.