Merge Two Sorted Lists
You are given the heads of two sorted linked lists `list1` and `list2`. Merge them into a single sorted linked list by re-linking the existing nodes (no new nodes). Return the head of the merged list. **Core Insight:** Use a dummy head node to simplify edge cases. Maintain a `current` pointer starting at the dummy. At each step compare the values at the fronts of both lists, attach the smaller node to `current.next`, and advance that list's pointer. When one list is exhausted, attach the remainder of the other list directly. **Algorithm:** Create `dummy` and `curr = dummy`. While both lists are non-empty: if `list1.val <= list2.val` attach `list1` and advance `list1`, else attach `list2` and advance `list2`. After the loop, set `curr.next` to whichever list still has nodes. Return `dummy.next`. **Why the dummy node helps:** It eliminates special-casing the very first node — we always write to `curr.next` uniformly. **Complexity:** Time O(m + n) — each node is visited once. Space O(1) — only pointer variables, no new nodes.
Constraints
- •
The number of nodes in both lists is in the range [0, 50] - •
-100 ≤ Node.val ≤ 100
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode:
dummy = ListNode(0)
curr = dummy
while list1 and list2:
if list1.val <= list2.val:
curr.next = list1
list1 = list1.next
else:
curr.next = list2
list2 = list2.next
curr = curr.next
curr.next = list1 or list2
return dummy.next