Alternate output between two linked lists

[beacon]

I'm writing a program that will alternate printing out data between two linked lists into a third list. Actually I have to write a function that will do it.

I wanted to test it out, so I created two lists with test number in them in main and started to write my function, but I have to pass the head pointer for each of the linked lists by reference and I'm stuck on what I need to do with the third pointer.

Anyway, if list 1 has the numbers 1, 3, 5, 7 and list 2 has the numbers 2, 4, 6, 8 the third list will print out 1, 2, 3, 4, 5, 6, 7, 8. Any extra values are to be omitted.

Here's what I've got so far:

#include <iostream>
 
using namespace std;
 
struct node{
    int data;
    node *next;
};
 
void interleave(node*,node*,node*);
 
void main(){
 
    node * head1;
    node * list1_1;
    list1_1 = new node;
    head1 = list1_1;
    list1_1->data = 2;
    list1_1->next = NULL;
 
    node * list1_2;
    list1_2 = new node;
    list1_2->data = 5;
    list1_1->next = list1_2;
    list1_2->next = NULL;
 
    node * list1_3;
    list1_3 = new node;
    list1_3->data = 7;
    list1_2->next = list1_3;
    list1_3->next = NULL;
 
    node * list1_4;
    list1_4 = new node;
    list1_4->data = 9;
    list1_3->next = list1_4;
    list1_4->next = NULL;
 
    //********************************************
 
    node * head2;
    node * list2_1;
    list2_1 = new node;
    head2 = list2_1;
    list2_1->data = 3;
    list2_1->next = NULL;
 
    node * list2_2;
    list2_2 = new node;
    list2_2->data = 6;
    list2_1->next = list2_2;
    list2_2->next = NULL;
 
    node * list2_3;
    list2_3 = new node;
    list2_3->data = 8;
    list2_2->next = list2_3;
    list2_3->next = NULL;
 
    //********************************************
 
    /*while(head1){
        cout<<head1->data<<endl;
        head1 = head1->next;
    }
 
    cout<<endl<<endl;
 
    while(head2){
        cout<<head2->data<<endl;
        head2 = head2->next;
    }*/
 
    interleave(head1,head2,head3);
 
}
 
void interleave(node*head1, node*head2, node*head3){
 
    while(head1 || head2 != NULL){
 
        node * head3;
        head3 = new node;
        head3 = head1;
        head3->next = head2;
        cout<<head3;
    }
}
 

[beacon]

This is kinda off the subject, but how do I get my code that I include in my questions to be color differently. I've seen it in other posts and was just curious.

[scruggsy]

void interleave(node*head1, node*head2, node*head3){
 
    while(head1 || head2 != NULL){
 
        node * head3;
        head3 = new node;
        head3 = head1;
        head3->next = head2;
        cout<<head3;
    }
}
 

Line 3: What are you trying to do with this expression? As written, the code inside your while loop will continue to execute as long as either head1 or head2 has a value other than NULL. This is fine if you know ahead of time that both lists have exactly the same number of elements; it is not fine if the number of elements can differ between the 2 lists. && instead of || would be safer.
Also, head1 and head2 have values (the addresses of your linked lists), and those values never change, so this loop will never terminate. If you are looking for the end of the list as a loop termination condition, you should be looking at the next members, not the heads of the lists.

Lines 5-6: Do you want to create a new linked list every time through the loop? It seems to me you want one new linked list, to which you will add 2 elements each time through your loop. head3 then should be declared and initialized outside of the loop.

Lines 7-8: Each time through your loop you are adding the first element of lists 1 and 2 to your new linked list. What you want to be doing is adding the next element of each list, each time through. Otherwise (assuming you fix the rest of this loop), you'll end up with an infinite list containing 2 3 2 3 2 3 2 3 2 3 .... Use the next member of lists 1 and 2 to traverse the lists.

Line 9: This will output the address of head3 as a number, which is probably not what you want. You probably want to display the data stored in one of head3's nodes.

Hope this helps. If not, keep asking. You will get it eventually.

EDIT: Use [ code=cpp] [ /code]

[beacon]

In line 5 and 6, are you saying that node * head3 AND head3 = new node should be intialize outside of the loop or just node * head3?

One thing I'm really not clear on is whether or not I have this set up to pass the parameters correctly. I have to use the three head pointers as parameters in my function, but I wasn't sure if I should do everything that I did with list 1 and 2 in the function or if it should stay where it is.

Thanks for the help scrug, by the way.

[scruggsy]

In line 5 and 6, are you saying that node * head3 AND head3 = new node should be intialize outside of the loop or just node * head3?

Well, think about it. You only need one new linked list. If you call head3 = new node inside your while loop, you'll overwrite what is stored in head3 each time through.
However, if you initialize head3 as a new node before the loop, you can then add nodes to it within your loop to create a list.
The important thing to remember is to keep track of the current node you are operating on within your loop. That way, you can do currentNode->next = new node to add a new element at the end of the list.

One thing I'm really not clear on is whether or not I have this set up to pass the parameters correctly. I have to use the three head pointers as parameters in my function, but I wasn't sure if I should do everything that I did with list 1 and 2 in the function or if it should stay where it is.

If your instructor wants you to pass three node*'s as params, then you've done the function header properly. But in that case there should be no need to declare a third node* head3 within the function, as it is passed as a parameter. Currently, in main() you are calling interleave(head 1, head2, head3) but head3 is never defined in main(), so this won't compile.

[beacon]

Ok...I think I'm almost set. Let me ask you this while I've got your attention. When I write the interleave function in main do I just type interleave(node *,node*,node*he ad3)? I got an error when I compiled with this and I guess I don't understand how I'm going to get the function going with the pointers in there.

We really didn't learn how to do this...we were given a take home assignment and kind of just asked to figure it out. I like that style most of the time, but with this it's been difficult.

By the way, here's my modified function:

void interleave(node*head1, node*head2, node*head3){
 
    head3 = new node;
    while(head1->next && head2->next != NULL){
 
        head3 = head1->next;
        head3->next = head2->next;
        cout<<head3->data;
    }
}
 

[scruggsy]

We really didn't learn how to do this...we were given a take home assignment and kind of just asked to figure it out. I like that style most of the time, but with this it's been difficult.

By the way, here's my modified function:

void interleave(node*head1, node*head2, node*head3){
 
    head3 = new node;
    while(head1->next && head2->next != NULL){
 
        head3 = head1->next;
        head3->next = head2->next;
        cout<<head3->data;
    }
}
 

Hmm, I'm surprised your instructor didn't explain this stuff. Linked lists are notorious for making students' heads spin. ;)
You are getting somewhere with this function.
However, remember the structure of a linked list: the list is formed by each node having a pointer to the next, which has a pointer to the next, etc until the end of the list.
So when adding a node to the end of the list, you need to know the last node:

lastNode->next = new node

Similarly, when traversing a list (going through the nodes one at a time), you get to the next node via currentNode->next
Look at your code: each time through the loop, you're doing head1->next, head2->next, and head3->next. These always give you the second element of the list. To get the third, you need to do secondNode->next; for the fourth, thirdNode->next.

So while you are traversing this list, you want to keep track of your current position in the list. Easiest way to do that is with head1 = head1->next, for instance. This way, each time through the loop you are dealing with the next element in the list, until no more remain. Same for head2 and for adding nodes to head3.

Does your textbook have illustrations or diagrams of linked lists? It's much easier to grasp if you can visualize it.

When I write the interleave function in main do I just type interleave(node *,node*,node*he ad3)? I got an error when I compiled with this and I guess I don't understand how I'm going to get the function going with the pointers in there.

You can't declare a variable within a function call. Declare it first, then pass it to your function.

[beacon]

I'm still confused. I added this to the function...but I'm not sure if this is where you're going or what you're trying to say.

void interleave(node*head1, node*head2, node*head3){
 
    head3 = new node;
    while(head1->next && head2->next != NULL){
 
        head3 = head1->next;
        head3->next = head2->next;
        head1 = head1->next;
        head2 = head2->next;
        cout<<head3->data;
    }
}
 

The book I have show linked lists embedded in classes and it's much different using them independently in a function, in my opinion. We've studied linked lists, but it's the pointer passing that we really didn't tackle. That's what's throwing me off my game.

With the code I've written above and with a function interleave(head 1,head2,head3) in main, I got zero errors, but nothing output to the screen.

[beacon]

Anybody else have any ideas what I'm doing wrong?

[beacon]

I got this to work, save for a debugging error after I executed, but I think that's only because the next value is NULL. If anyone know how to fix this let me know, otherwise I'm finished working on it.