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
#include
#include

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->next;
free(tmp);
}
}

List* generateList(int len) {
List* head = NULL;
List* tail = NULL;
int i;
for (i = 0; i item = i;
node->next = NULL;
if ( !head ) {
head = node;
tail = node;
} else {
tail->next = node;
tail = node;
}
}
return head;
}

vo

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 && b ) {
        List* oldNextA = a->next;
        List* oldNextB = b->next;
        a->next = b;
        b->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->next;
        a->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.

StackExchange Code Review Q#77682, answer score: 2