Merge Sorted Lists

Merging Two Sorted Linked Lists

Given two sorted lists, produce one merged sorted list by splicing together existing nodes — no new allocation needed.

struct Node *merge_sorted(struct Node *a, struct Node *b) {
    struct Node dummy;
    struct Node *tail = &dummy;
    dummy.next = NULL;
    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;
}

The Dummy Head Trick

A dummy (sentinel) node before the real head lets you avoid special-casing the first node. You always append to tail->next and advance tail. At the end, dummy.next is the real head.

Draining the Remainder

When one list is exhausted, the other is already sorted — attach it directly with tail->next = a != NULL ? a : b.

Example

a: [1] -> [3] -> [5] -> NULL
b: [2] -> [4] -> [6] -> NULL

Compare 1 vs 2 → take 1   tail: dummy->[1]
Compare 3 vs 2 → take 2   tail: dummy->[1]->[2]
Compare 3 vs 4 → take 3   tail: dummy->[1]->[2]->[3]
Compare 5 vs 4 → take 4   tail: dummy->[1]->[2]->[3]->[4]
Compare 5 vs 6 → take 5   tail: ...->[5]
Compare (a done) vs 6 → attach b
Result: [1]->[2]->[3]->[4]->[5]->[6]->NULL

Your Task

Implement struct Node *merge_sorted(struct Node *a, struct Node *b) that merges two sorted lists and returns the head of the merged list.