Merge Two Sorted Lists

easy linked list two pointers

Problem

Two singly linked lists are individually sorted in non-decreasing order. Splice them together — without allocating new nodes — into a single sorted list and return its head.

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(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 merge(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 merge(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* merge(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;
}

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