4
\$\begingroup\$

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 <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

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 < len; i++) {
        List* node = malloc(sizeof(*node));
        node->item = i;
        node->next = NULL;
        if ( !head ) {
            head = node;
            tail = node;
        } else {
            tail->next = node;
            tail = node;
        }
    }
    return head;
}

void printList(List* list) {
    while ( list ) {
        printf("%d ", list->item);
        list = list->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->next ) {
        list->next = prev;
        return list;
    } else {
        List* next = list->next;
        list->next = prev;
        return reverseList_rec_imp(next, list);
    }
}

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

List* zipLists_rec_top(List* a, List* b) {
    List* oldNext = a->next;
    a->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->next = zipLists_rec_bot(b, a->next);
        return a;
    }
}
\$\endgroup\$
2
\$\begingroup\$

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.

  1. save away item 2 from listA
  2. make item 1 on listB the new item 2 on listA
  3. make the saved-away item 2 (now orphaned) the swapped list B
  4. 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.

\$\endgroup\$
  • \$\begingroup\$ Being aware of the space complexity concern, the recursive solutions were 'for fun' as it were; definitely would do a conversion to iterative if I ever had to write a recursive solution for larger scaled applications. The c99 standard was more to muck with for (int i = 0.... Other than that, I'm glad you mentioned the optimization involving the excess variables. I also like how a and b being NULL are defended against without having a bland if (!a || !b) return NULL; statement. Thanks for your comments! \$\endgroup\$ – rjs Jan 16 '15 at 6:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.