creating an interleave_lists linked list?

Question

I'm trying to create a linked list function called IntNode *interleave_lists(IntNode *head_1, IntNode *head_2); that takes two linked list, combines them and return a pointer to the head.

example: suppose head_1 points to a linked list containing three integers: 1, 3, 5, and head_2 points to a linked list containing 5 integers: 10, 11, 12, 13, 14. The new linked list will contain 8 integers, in this order: 1, 10, 3, 11, 5, 12, 13, 14.

I have these structs to help create the linked list:

struct intnode {
   int value;
   struct intnode *next;
};
typedef struct intnode IntNode;

IntNode *intnode_construct(int value, IntNode *next)
{
   IntNode *p = malloc(sizeof(IntNode));
   assert (p != NULL);
   p->value = value;
   p->next = next;
   return p;
}
void print_linked_list(IntNode *p) //for printing linked list
{
    if (p == NULL) {
        printf("empty list");
        return; 
    }

    /* Print every node in the linked list except the last one,
       using the format: value1 -> value2 -> value3 -> ...
     */
    for (; p->next != NULL; p = p->next) {
        printf("%d -> ", p->value);
    }

    /* Print the last node. */
    printf("%d", p->value);
}

now trying to create the function I have:

IntNode *interleave_lists(IntNode *head_1, IntNode *head_2)
{
    int count = 1;
    IntNode *p1=head_1, *p2=head_2,*head=NULL;
    for(; (p1->next != NULL) || (p2->next != NULL); p1 = p1->next, p2 = p2->next){
        if(p1 != NULL && count == 1){
            head = intnode_construct(p1->value,head);
            count = 0;
        } else if(p2 != NULL && count == 0){
            head = intnode_construct(p2->value,head);
        }
    }
    return head;
}

but every time I run it the console displays CRT: unhandled exception (main) -- terminating. My test case for this function:

int main(void)
{
    IntNode *list1 = NULL,*list2 = NULL; // An empty linked list.
    list1 = intnode_construct(5, list1);
    list1 = intnode_construct(3, list1);
    list1 = intnode_construct(1, list1);

    list2 = intnode_construct(14, list2);
    list2 = intnode_construct(13, list2);
    list2 = intnode_construct(12, list2);
    list2 = intnode_construct(11, list2);
    list2 = intnode_construct(10, list2);


    IntNode *head = NULL;

    head = interleave_lists(list1, list2);
    print_linked_list(head);
}

Answer 1

Multiple problems

• You check p->next != NULL rather than p != NULL, so you lose the last element of the list
• Your loop checks p1 || p2, looping as long as either pointer hasn't yet reached the end. So if the lists are different lengths, the pointer for the short list will run off the end and crash.
• your intnode_construct function constructs lists from right to left (tail to head), but you iterate from head to tail, so you are reversing the lists as you interleave them.

The reversing lists thing means you need to interleave from the tail, making your interleave_lists function much easier to implement recursively:

IntNode *copy_list(IntNode *head)
{
    if (!head) return head;
    return intnode_construct(head->value, copy_list(head->next));
}

IntNode *interleave_lists(IntNode *head_1, IntNode *head_2)
{
    if (!head_1) return copy_list(head_2);
    return intnode_construct(head_1->value, interleave_lists(head_2, head_1->next));
}

Alternately, you can do a 'destructive' interleave, reusing the nodes of the input lists:

IntNode *interleave_lists(IntNode *head_1, IntNode *head_2)
{
    if (!head_1) return head_2;
    head_1->next = interleave_lists(head_2, head_1->next);
    return head_1;
}