Zip / merge two linked lists together The following code interweaves two linked lists together in three flavors: iterative, recursive top-down, and recursive bottom-up. My iterative solution feels like it can be optimized better and my bottom up recursive design skills are not necessarily the best (although this solution is a much smaller task than most recursive bottom up solutions e.g. pruning a binary search tree). 

#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;stdbool.h&gt;

typedef struct list List;
struct list {
    int item;
    List* next;
};

//setup functions
List* generateList(int len);
void freeList(List* list);
void printList(List* list);
void showcase();
//zip functions
List* zipLists_iter(List* a, List* b);
List* zipLists_rec_top(List* a, List* b);
List* zipLists_rec_bot(List* a, List* b);
List* reverseList_rec(List* list);
List* reverseList_rec_imp(List* list, List* prev);

int main() {
    showcase();
    return EXIT_SUCCESS;
}

void showcase() {
    List* a = generateList(5);
    List* b = generateList(5);
    b = reverseList_rec(b);
    printList(a); //These are here for simplicity
    printList(b);

    puts("Testing zipLists_iter");
    a = zipLists_iter(a, b);
    printList(a);
    freeList(a);

    a = generateList(5);
    b = generateList(5);
    b = reverseList_rec(b);
    puts("Testing zipLists_rec_top");
    a = zipLists_rec_top(a, b);
    printList(a);
    freeList(a);

    a = generateList(5);
    b = generateList(5);
    b = reverseList_rec(b);
    puts("Testing zipLists_rec_bot");
    a = zipLists_rec_bot(a, b);
    printList(a);
    freeList(a);
}


void freeList(List* list) {
    while ( list ) {
        List* tmp = list;
        list = list-&gt;next;
        free(tmp);
    }
}

List* generateList(int len) {
    List* head = NULL;
    List* tail = NULL;
    int i;
    for (i = 0; i &lt; len; i++) {
        List* node = malloc(sizeof(*node));
        node-&gt;item = i;
        node-&gt;next = NULL;
        if ( !head ) {
            head = node;
            tail = node;
        } else {
            tail-&gt;next = node;
            tail = node;
        }
    }
    return head;
}

void printList(List* list) {
    while ( list ) {
        printf("%d ", list-&gt;item);
        list = list-&gt;next;
    }
    printf("\n");
}

List* reverseList_rec(List* list) {
    return reverseList_rec_imp(list, NULL);
}

List* reverseList_rec_imp(List* list, List* prev) {
    if (!list) return NULL; //mirror NULL input

    if ( !list-&gt;next ) {
        list-&gt;next = prev;
        return list;
    } else {
        List* next = list-&gt;next;
        list-&gt;next = prev;
        return reverseList_rec_imp(next, list);
    }
}

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;
}

List* zipLists_rec_top(List* a, List* b) {
    List* oldNext = a-&gt;next;
    a-&gt;next = b;
    if ( b )
        zipLists_rec_top(b, oldNext);
    return a;
}

List* zipLists_rec_bot(List* a, List* b) {
    if ( !a ) {
        return b;
    } else if ( !b ) {
        return a;
    } else {
        a-&gt;next = zipLists_rec_bot(b, a-&gt;next);
        return a;
    }
}
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.