Merge Two Sorted Lists

easy linked list two pointers

Problem

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

Use a dummy head node so the first append needs no special case. Walk a tail pointer along the result, picking whichever of the two list heads has the smaller value.

Inputa = [1, 4, 7], b = [2, 3, 8, 9]

Output[1, 2, 3, 4, 7, 8, 9]

a (sorted, comma-separated)

b (sorted, comma-separated)

def merge_two_lists(a, b):
    dummy = ListNode()
    tail = dummy
    while a and b:
        if a.val <= b.val:
            tail.next = a
            a = a.next
        else:
            tail.next = b
            b = b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next

function mergeTwoLists(a, b) {
  const dummy = { val: 0, next: null };
  let tail = dummy;
  while (a && b) {
    if (a.val <= b.val) { tail.next = a; a = a.next; }
    else { tail.next = b; b = b.next; }
    tail = tail.next;
  }
  tail.next = a || b;
  return dummy.next;
}

class Solution {
    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        while (a != null && b != null) {
            if (a.val <= b.val) { tail.next = a; a = a.next; }
            else { tail.next = b; b = b.next; }
            tail = tail.next;
        }
        tail.next = (a != null) ? a : b;
        return dummy.next;
    }
}

ListNode* mergeTwoLists(ListNode* a, ListNode* b) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (a && b) {
        if (a->val <= b->val) { tail->next = a; a = a->next; }
        else { tail->next = b; b = b->next; }
        tail = tail->next;
    }
    tail->next = a ? a : b;
    return dummy.next;
}

Explanation

Both lists are already sorted, so merging them is like the zipper step of merge sort: keep comparing the two front nodes and always take the smaller one. You never need to look further than the two current heads.

A dummy head removes the awkward special case for the very first node, and a tail pointer marks where the next node should be attached. While both lists still have nodes, we compare a.val and b.val, splice the smaller node onto tail, and advance that list.

When one list runs out, the other is already sorted, so we just attach whatever remains with tail.next = a or b. No more comparing needed.

Example: a = [1, 4, 7], b = [2, 3, 8, 9]. Take 1 (from a), then 2 and 3 (from b), then 4 and 7 (from a), then the leftover 8, 9. Result: [1, 2, 3, 4, 7, 8, 9].

Notice we reuse the existing nodes by relinking pointers rather than creating new ones, so the extra memory stays constant.

Time: O(n + m) Space: O(1)