Zip / merge two linked lists together
The iterative approach is likely the most efficient approach. It is sparing on memory allocation, it does not require stack manipulation (and frames), and it won't cause stack overflows for long lists.

The recursive options are really not worth considering for this problem.

Your iterative implementation is not as 'tight' as I would hope, though. Consider your code:


List* zipLists_iter(List* a, List* b) {
    List* root = a;
    while ( a &amp;&amp; b ) {
        List* oldNextA = a-&gt;next;
        List* oldNextB = b-&gt;next;
        a-&gt;next = b;
        b-&gt;next = oldNextA;
        a = oldNextA;
        b = oldNextB;
    }
    return root;
}



Your code saves away the 'second' items. It cross links the current items, and then it advances both lists.

I would prefer a solution that does one item at a time (instead of 2), and then swaps the lists so that the second list becomes the first, and vice versa.


save away item 2 from listA
make item 1 on listB the new item 2 on listA
make the saved-away item 2 (now orphaned) the swapped list B
make what was the listB item 1 the new listA.


In code, it would look like:

List* zipLists_iter(List* a, List* b) {
    if (!a) {
        return b;
    }
    List* root = a;
    while ( b ) {
        List* tmp = a-&gt;next;
        a-&gt;next = b;
        a = b;
        b = tmp;
    }
    return root;
}


Note that I put a check in there for an empty List A. This allows it to work on unevenly sized lists, including an empty list A.

By thinking about the problem a little differently you can:


remove a temporary variable.
remove two assignments
remove a null-check (a is never null)
but, you loop more often.


The remainder of your code (excluding the recursion methods which I am not going to review) is really good in terms of neatness, and functionality. It was easy to follow, and it was great that I could compile and run your code without any issues, even when using -Wall, and compiling as C99 standard.

Nicely done.