MHB Both fields point to the same element

[evinda]

Hello! (Wave)

Given the following two lists:

View attachment 3442

what could we do, so that the first list contains both the elements of the first and the second list, sorted? (Thinking)

I wrote the following algorithm:

pointer *P=L1, *Q=L2,n; 

while ((P != '\0') && ( Q != '\0')){  
         n->data=Q->data; 
         n->next=P; 
         Q=Q->next; 
}

But, then it is like that:

View attachment 3443

The next fields of $1$ and $5$ point both to $100$, but it shouldn't be like that... (Worried)

What could we do? (Thinking)

 

[I like Serena]

Hey! (Wave)

pointer *P=L1, *Q=L2,n;

I'm assuming L1 is a pointer to the first element of the first list, yes? (Wondering)
And L2 is a pointer to the first element of the second list?If so, then when you define [m]pointer *P[/m] that makes P a pointer to a [m]pointer[/m].
But then you can't assign L1 to it.

Can it be that it should be: [m]pointer P=L1, Q=L2, n;[/m]? (Wondering)

while ((P != '\0') && ( Q != '\0')){

The value [m]'\0'[/m] represents a character with value zero.
But P is a pointer.
You're not suppose to compare a pointer to a character!

Better would be: [m]while ((P != NULL) && ( Q != NULL)){[/m]

         n->data=Q->data; 
         n->next=P; 
         Q=Q->next; 
}

But, then it is like that:

The next fields of $1$ and $5$ point both to $100$, but it shouldn't be like that... (Worried)

What could we do? (Thinking)

Apparently you want to move the first element of L2 to L1, such that it comes before its first element.

The right way to do that is:

Q = L2;                   // Make Q point to the element that we want to move
L2 = L2->next;
Q->next = L1;
L1 = Q;

How will the pointers look after this snippet of code? (Wondering)

 

[evinda]

Hey! (Wave)
I'm assuming L1 is a pointer to the first element of the first list, yes? (Wondering)
And L2 is a pointer to the first element of the second list?If so, then when you define [m]pointer *P[/m] that makes P a pointer to a [m]pointer[/m].
But then you can't assign L1 to it.

Can it be that it should be: [m]pointer P=L1, Q=L2, n;[/m]? (Wondering)

The value [m]'\0'[/m] represents a character with value zero.
But P is a pointer.
You're not suppose to compare a pointer to a character!

Better would be: [m]while ((P != NULL) && ( Q != NULL)){[/m]

Apparently you want to move the first element of L2 to L1, such that it comes before its first element.

The right way to do that is:

Q = L2;                   // Make Q point to the element that we want to move
L2 = L2->next;
Q->next = L1;
L1 = Q;

How will the pointers look after this snippet of code? (Wondering)

Would it be maybe better to use NODE, instead of pointer, like that? (Thinking)

NODE *P=L1, *Q=L2,n; 
while ((P != NULL) && (Q != NULL)){ 
         n=newcell(NODE); 
         n->data=Q->data; 
         n->next=P; 
         P=P->next; 
}

 

[I like Serena]

Would it be maybe better to use NODE, instead of pointer, like that? (Thinking)

NODE *p1=L1, *p2=L2,n; 
while ((p1 != NULL) && (p2 != NULL)){ 
         n=newcell(NODE); 
         n->data=p2->data; 
         n->next=p1; 
         p2=p2->next; 
}

Yep! (Smile)

Btw, you still need to update L1 (the head), since the head of that list changed.
As it is now, after the first iteration, L1 still points to what is now the second element of the list. (Worried)

 

[evinda]

Btw, you still need to update L1 (the head), since the head of that list changed.
As it is now, L1 still points to what is now the second element of the list. (Worried)

How could I do this? (Thinking)

 

[I like Serena]

How could I do this? (Thinking)

Add [m]L1 = n;[/m].

Suppose you draw a diagram showing the pointers after the first iteration? (Wondering)

 

[evinda]

Add [m]L1 = n;[/m].

Suppose you draw a diagram showing the pointers after the first iteration? (Wondering)

I added also an other if, for the case, when $P.data< Q.data$ and I got the following diagram:

View attachment 3444

 

[I like Serena]

Looking good. (Smile)

The brown arrow representing L1 should keep moving to such that it consistently points the the beginning of the list though. (Wasntme)

 

[evinda]

Looking good. (Smile)

The brown arrow representing L1 should keep moving to such that it consistently points the the beginning of the list though. (Wasntme)

Doesn't this arrow move when this:

 if (P -> data< Q->data){
              if (P->next->data < Q->data){
                  P=P->next;
               }
           }

is executed? (Thinking) Or am I wrong? (Thinking)

 

[I like Serena]

Doesn't this arrow move when this:

 if (P -> data< Q->data){
              if (P->next->data < Q->data){
                  P=P->next;
               }
           }

is executed? (Thinking) Or am I wrong? (Thinking)

Since none of that code changes L1, how can the brown arrow move? (Worried)

 

[evinda]

Since none of that code changes L1, how can the brown arrow move? (Worried)

At the beginning I wrote:

NODE *P=L1;
NODE *Q=L2;

Am I wrong? (Thinking)

 

[I like Serena]

At the beginning I wrote:

NODE *P=L1;
NODE *Q=L2;

Am I wrong? (Thinking)

P and L1 are independent pointers.
That code makes P initially point to the same element as L1 points to.
Changing P won't make L1 change. (Worried)

 

[evinda]

P and L1 are independent pointers.
That code makes P initially point to the same element as L1 points to.
Changing P won't make L1 change. (Worried)

Add [m]L1 = n;[/m].

I added the command

P=n;

in order that the List L1 does not change. Shouldn't I do it like that? (Worried)

At the diagram, I thought that the brown arrow shows to the element to which the pointer P points. Isn't it like that? (Thinking)

 

[I like Serena]

I added the command

P=n;

in order that the List L1 does not change. Shouldn't I do it like that? (Worried)

Hmm... I guess you could.
I guess there is no real need to change L1.
At the end you can simply return P, satisfying the problem statement. (Thinking)

At the diagram, I thought that the brown arrow shows to the element to which the pointer P points. Isn't it like that? (Thinking)

I though you had a red arrow for P.
Perhaps you should label the arrows then. (Wasntme)

 

[evinda]

Hmm... I guess you could.
I guess there is no real need to change L1.
At the end you can simply return P, satisfying the problem statement. (Thinking)

A ok! (Nod)

I though you had a red arrow for P.
Perhaps you should label the arrows then. (Wasntme)

At the first list, the red arrows show which element is the next one, each time, and the brown arrow is the pointer P. At the second list, the brown arrow is the pointer Q. (Thinking)

And something else.. if the pointer P shows at the last element and P.next==NULL and Q != NULL, do we have to create a new NODE for each remaining element of the second list or could we just do it like that: P.next=Q ? (Thinking)

 

[I like Serena]

At the first list, the red arrows show which element is the next one, each time, and the brown arrow is the pointer P. At the second list, the brown arrow is the pointer Q. (Thinking)

And something else.. if the pointer P shows at the last element and P.next==NULL and Q != NULL, do we have to create a new NODE for each remaining element of the second list or could we just do it like that: P.next=Q ? (Thinking)

The problem statement doesn't say anything about whether the second list should remain as is or not.
So you can choose. (Smile)
Actually, it appears you don't have to create any nodes - you might simply move the nodes in the 2nd list to the first list instead of creating copies. (Wasntme)

 

[evinda]

The problem statement doesn't say anything about whether the second list should remain as is or not.
So you can choose. (Smile)
Actually, it appears you don't have to create any nodes - you might simply move the nodes in the 2nd list to the first list instead of creating copies. (Wasntme)

So, could I just write command

P.next=Q;

or do I have to use also head and tail, in this case? (Thinking)

 

[I like Serena]

In this particular case you could do all that is required with:

L2.tail.next = L1.head
L1.head = L2.head

(Wasntme)

 

[evinda]

In this particular case you could do all that is required with:

L2.tail.next = L1.head
L1.head = L2.head

(Wasntme)

Why is it like that? (Worried) Shouldn't we put the remaining elements of the second list to the first one? Or am I wrong? (Thinking)

 

[I like Serena]

Why is it like that? (Worried) Shouldn't we put the remaining elements of the second list to the first one? Or am I wrong? (Thinking)

We are putting all elements of the second list in the first one.

Since in this particular case both lists are already sorted, and the second has only values lower than the first list, I believe we can simply append them.

 

[evinda]

We are putting all elements of the second list in the first one.

Since in this particular case both lists are already sorted, and the second has only values lower than the first list, I believe we can simply append them.

But shouldn't it be then like that:

L1.tail.next=L2.head;
L1.tail=L2.tail;

Will the remaining elements of the second list not be greater that the elements of the first list? (Thinking)

Or am I wrong? (Worried)

 

[I like Serena]

But shouldn't it be then like that:

L1.tail.next=L2.head;
L1.tail=L2.tail;

Will the remaining elements of the second list not be greater that the elements of the first list? (Thinking)

Or am I wrong? (Worried)

That way the elements are not sorted.
Because in the problem statement the elements in the second list have lower values.

 

[evinda]

That way the elements are not sorted.
Because in the problem statement the elements in the second list have lower values.

I meant a case like this one:

View attachment 3451

How can we put the remaining elements of the second list at the first list? (Thinking)

 

[I like Serena]

I meant a case like this one:

https://www.physicsforums.com/attachments/3451

How can we put the remaining elements of the second list at the first list? (Thinking)

Oh! You want to make it work for a more general case!? (Wait)

Can we assume that L1 and L2 are sorted? (Wondering)
You didn't specify.

 

[evinda]

Oh! You want to make it work for a more general case!? (Wait)

Can we assume that L1 and L2 are sorted? (Wondering)
You didn't specify.

Yes, it is given that L1 and L2 are sorted. (Nod)

 

[I like Serena]

Yes, it is given that L1 and L2 are sorted. (Nod)

Ah. Then I misunderstood your problem statement. (Doh)

So in that case we can't simply append the lists.
We'll have to go through them 1 by 1 and insert elements from L2 in between elements of L1.
And we'll have to take care when those elements get inserted at either the head of L1 or its tail.

 

[evinda]

Ah. Then I misunderstood your problem statement. (Doh)

So in that case we can't simply append the lists.
We'll have to go through them 1 by 1 and insert elements from L2 in between elements of L1.
And we'll have to take care when those elements get inserted at either the head of L1 or its tail.

In the case of the post #23, shouldn't all the elements of L2 get inserted after the last element of L1? (Thinking)

 

[I like Serena]

In the case of the post #23, shouldn't all the elements of L2 get inserted after the last element of L1? (Thinking)

Yes. (Nod)

 

[evinda]

Yes. (Nod)

Do we have to do it like that?

if (P!=NULL && P.next==NULL){
    while (Q != NULL){
             N=addnode(node);
             N.data=Q.data;
             N.next=NULL;
             P.next=N;
             P=N;
             Q=Q.next;
    }
}

(Thinking)

 

[I like Serena]

Do we have to do it like that?

if (P!=NULL && P.next==NULL){
    while (Q != NULL){
             N=newcell(node);
             N.data=Q.data;
             N.next=NULL;
             P.next=N;
             P=N;
             Q=Q.next;
    }
}

(Thinking)

Yep.
That would work to append a copy of the values starting from Q and after, to the end of L1. (Smile)