Back to solutions

Merge Two Sorted Lists

EasyLinked List

Merge two sorted linked lists into one sorted list and return its head.

Open problem
Constraints
  • 0 <= each list length <= 50
  • -100 <= Node.val <= 100

Dummy head and splice

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

Use a dummy node and a tail pointer. Repeatedly attach the smaller of the two list heads to the tail, then append whatever remains.

struct ListNode { int val; ListNode* next; };

ListNode* mergeTwoLists(ListNode* a, ListNode* b) {
    ListNode dummy(0), *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;
}