</>EmbeddedInterview

Merge two sorted linked lists.

Easy"Coding: Linked Lists, Stacks & Queues"
node_t *merge_sorted(node_t *a, node_t *b)
{
    node_t dummy = { 0, NULL }, *tail = &dummy;
    while (a && b) {
        if (a->val <= b->val) { tail->next = a; a = a->next; }   /* <= keeps it stable */
        else                  { tail->next = b; b = b->next; }
        tail = tail->next;
    }
    tail->next = a ? a : b;                       /* append the remainder */
    return dummy.next;
}

Points: a dummy head node removes special cases; reuses the existing nodes (no allocation), O(n + m) time, O(1) space; this is the merge step of merge sort on lists.