MHB Creating List $L_3$ from $L_1,L_2$ w/ $O(n_1+n_2)$ Complexity

[evinda]

Hello! (Wave)

Given two lists, $L_1$ with $n_1$ elements and $L_2$ with $n_2$ elements, I want to write an algorithm that creates a new list $L_3$, for which the following stand:

• The elements at the odd positions of $L_3$ are these that are at the even positions of $L_1$
• The elements at the even positions of $L_3$ are the last $\frac{n_1}{2}$ elements of $L_2$

$n_1,n_2$ can be any even numbers. The time complexity of the algorithm should be $O(n_1+n_2)$.

Could you give me a hint how I could do this? (Thinking)

 

[I like Serena]

Hello! (Wave)

Given two lists, $L_1$ with $n_1$ elements and $L_2$ with $n_2$ elements, I want to write an algorithm that creates a new list $L_3$, for which the following stand:

• The elements at the odd positions of $L_3$ are these that are at the even positions of $L_1$
• The elements at the even positions of $L_3$ are the last $\frac{n_1}{2}$ elements of $L_2$

$n_1,n_2$ can be any even numbers. The time complexity of the algorithm should be $O(n_1+n_2)$.

Could you give me a hint how I could do this? (Thinking)

Hi! (Happy)

Alternate between adding even elements from $L_1$ and adding elements of the last $\frac{n_1}{2}$ from $L_2$? (Wondering)

Something like:

Solve problem(L1, L2)
    L3 ← empty
    Skip the right number of elements in L2
    while not done
        Add next element from L1 to L3
        Skip next element (that is at an odd position) in L1
        Add next element from L2 to L3
    return L3

This will need some refinement though. (Thinking)

 

[evinda]

Hi! (Happy)

Alternate between adding even elements from $L_1$ and adding elements of the last $\frac{n_1}{2}$ from $L_2$? (Wondering)

Something like:

Solve problem(L1, L2)
    L3 ← empty
    Skip the right number of elements in L2
    while not done
        Add next element from L1 to L3
        Skip next element (that is at an odd position) in L1
        Add next element from L2 to L3
    return L3

This will need some refinement though. (Thinking)

Can we skip the right number of elements in L2, like that?

Solve problem(L1, L2)
    pointer L3 ← empty,p=L1,q=L2;
    int i;
    for (i=0; i<n1; i++) q=q->next

(Thinking)

 

[I like Serena]

Can we skip the right number of elements in L2, like that?

Solve problem(L1, L2)
    pointer L3 ← empty,p=L1,q=L2;
    int i;
    for (i=0; i<n1; i++) q=q->next

(Thinking)

That would skip the first $n_1$ entries in $L_2$.
... but we need the last $\frac {n_1}2$ entries, while the total number of entries is $n_2$. (Worried)
So I think we should skip only $n_2 - \frac {n_1}2$ entries. (Thinking)

 

[evinda]

That would skip the first $n_1$ entries in $L_2$.
... but we need the last $\frac {n_1}2$ entries, while the total number of entries is $n_2$. (Worried)
So I think we should skip only $n_2 - \frac {n_1}2$ entries. (Thinking)

So, should it be like that? (Thinking)

Solve problem(L1, L2){
    pointer L3 ← empty,q=L2;
    int i,j;
    for (i=0; i<n2-n1/2; i++) q=q->next;
    for (j=0; j<(n1+n2)/2; j++){
         L3->data=L1->next->data;
         L3=L3->next;
         L3->data=q->data;

    }    
    return L3;
}

Or have I done something wrong? (Thinking)

 

[I like Serena]

Solve problem(L1, L2){
    pointer L3 ← empty,q=L2;
    int i,j;
    for (i=0; i<n2-n1/2; i++) q=q->next;
    for (j=0; j<(n1+n2)/2; j++){
         L3->data=L1->next->data;
         L3=L3->next;
         L3->data=q->data;

    }    
    return L3;
}

Suppose we pick L1={1,2} and L2={7,8}, can you predict what your algorithm will do? (Wondering)

 

[evinda]

Suppose we pick L1={1,2} and L2={7,8}, can you predict what your algorithm will do? (Wondering)

The first element of $L_3$ will be 1, and the second will be NULL, right? (Thinking)

So, should it be maybe like that?

Solve problem(L1, L2){
    pointer L3 ← empty,q=L2;
    int i,j;
    for (i=0; i<n2-n1/2-1; i++) q=q->next;
    for (j=0; j<(n1+n2)/4; j++){
         L3->data=L1->next->data;
         L3=L3->next;
         L3->data=q->next->data;

    } 
    L3->next=NULL;   
    return L3;
}

Or am I wrong?

 

[I like Serena]

The first element of $L_3$ will be 1, and the second will be NULL, right? (Thinking)

So, should it be maybe like that?

Solve problem(L1, L2){
    pointer L3 ← empty,q=L2;
    int i,j;
    for (i=0; i<n2-n1/2-1; i++) q=q->next;

It looks as if q will be pointer to the right element here. (Smile)
Although I didn't check any potential plus or minus 1 issues yet.

    for (j=0; j<(n1+n2)/4; j++){

I don't think [m](n1+n2)/4[/m] is the proper end condition.
It may be better to eliminate the end condition here, but check each time we want to process something, check if we can, and if not, take appropriate action. (Thinking)

Typically, we want to check if a pointer is NULL before accessing it.
That is also the right moment to handle the case that it is NULL, and we need to do something special. (Nerd)

         L3->data=L1->next->data;
         L3=L3->next;

This will cause chaos and madness. (Crying)
The first time round L3 is empty, meaning we cannot access L3->data, nor L3->next.
We can also not be sure that L1->next is different from NULL, so this will also cause an access violation. (Crying)

         L3->data=q->next->data;

Since neither L1, nor q is ever changed, the same values will be used every time.
I think there should be statements that will bring us to the next element of L1 respectively L2. (Wasntme)

    } 
    L3->next=NULL;

When we will have constructed L3 properly, it will point to a long linked list.
Assigning L3->next to NULL will effectively throw the whole list away, keeping only the first.
I think that is not right. (Worried)