loading

21. Merge Two Sorted Lists — Step-by-Step Visualization

easyLeetCode #21Linked List

You are given the heads of two sorted linked lists `list1` and `list2`. Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list. **Example 1:** Input: `list1 = [1,2,4], list2 = [1,3,4]` Output: `[1,1,2,3,4,4]` **Example 2:** Input: `list1 = [], list2 = []` Output: `[]` **Example 3:** Input: `list1 = [], list2 = [0]` Output: `[0]`

Algorithm Pattern

Two Pointers + Dummy Node

Key Idea

Use a dummy node to easily establish the new list's head, and simply attach the smaller of the two incoming list nodes as you walk through them parallelly.

Step-by-Step Approach

  1. Initialize a dummy node and a `tail` pointer starting at the dummy.
  2. While both `list1` and `list2` have nodes left, compare their heads.
  3. If `list1.val < list2.val`, wire `tail.next = list1` and advance `list1`.
  4. Else, wire `tail.next = list2` and advance `list2`.
  5. Advance `tail`.
  6. If one list gets exhausted before the other, just wire `tail.next` to the remaining list.
  7. Return `dummy.next`.

Common Gotchas

  • Don't complicate the loop condition! Once one list exhausts, the loop can terminate and the remainder of the other list can be appended natively in O(1) step.

Related Problems

← All problems