# Merge Two Sorted Lists

- **Canonical ID**: `merge-two-sorted-lists`
- **Canonical URL**: https://dsacheatsheet.com/problems/merge-two-sorted-lists
- **Difficulty**: easy
- **Patterns**: Linked Lists
- **Version**: 1.0.0 (verified 2026-11-11T21:15:00Z)
- **Original Problem**: https://leetcode.com/problems/merge-two-sorted-lists/

## 1. Core Invariant / The Trick

Anchor the output with a `dummy` sentinel node and a `tail` pointer. Repeatedly attach the smaller of `l1` and `l2`, then splice whichever tail remains non-null in O(1).

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N + M)`
- **Space Complexity**: `O(1)`
- **Proof**: Each comparison advances one pointer until at least one list finishes; existing nodes are relinked in place.

## 3. Minimal Idiomatic Code

### Python
```python
def mergeTwoLists(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    dummy = tail = ListNode()
    while l1 and l2:
        if l1.val <= l2.val:
            tail.next, l1 = l1, l1.next
        else:
            tail.next, l2 = l2, l2.next
        tail = tail.next
    tail.next = l1 or l2
    return dummy.next
```

### TypeScript
```typescript
export function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  const dummy = new ListNode(0);
  let tail = dummy;
  while (l1 && l2) {
    if (l1.val <= l2.val) {
      tail.next = l1;
      l1 = l1.next;
    } else {
      tail.next = l2;
      l2 = l2.next;
    }
    tail = tail.next;
  }
  tail.next = l1 ?? l2;
  return dummy.next;
}
```

### C++
```cpp
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0), *tail = &dummy;
    while (l1 && l2) {
        if (l1->val <= l2->val) { tail->next = l1; l1 = l1->next; }
        else { tail->next = l2; l2 = l2->next; }
        tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;
    return dummy.next;
}
```

### Java
```java
ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), tail = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) { tail.next = l1; l1 = l1.next; }
        else { tail.next = l2; l2 = l2.next; }
        tail = tail.next;
    }
    tail.next = l1 != null ? l1 : l2;
    return dummy.next;
}
```

### Go
```go
func mergeTwoLists(l1, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    tail := dummy
    for l1 != nil && l2 != nil {
        if l1.val <= l2.val {
            tail.next, l1 = l1, l1.next
        } else {
            tail.next, l2 = l2, l2.next
        }
        tail = tail.next
    }
    if l1 != nil { tail.next = l1 } else { tail.next = l2 }
    return dummy.next
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Writing separate head initialization logic causes null-pointer edge bugs on empty inputs.
- Iterating instead of splicing the remaining non-null list wastes loop iterations.

### Follow-ups
- Generalizes directly to Merge k Sorted Lists via min-heap or divide-and-conquer pairwise merging.