Merge two sorted linked lists.
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.