CODEWITHSUNDEEP
cstructlinked-list
Bourezg
Bourezg

Reputation: 59

Merging two unsorted linked lists?

If I start with a struct:

typedef struct list
{
    int data;
    struct list *next;
} node;

How would I merge two of these structures, lets say the two are X and Y, respectively and a resultant called Z. I want the merge to consist of x1 pointing to Y1 pointing to X2 pointing to Y2 pointing to X3... until the last Y is used. If one list has more than the other, just put the remaining on the end. Lastly, no allocating memory, just use the nodes already in use (in other words just changing the pointers of each element to point to the right place). This is what I would like it to look like:

X: 1->5->6->3->10->11
Y: 2->8->4->9
Z: 1->2->5->8->6->4->3->9->10->11

right now, I am trying to recurse through it, but I cant get it to work

node *list_copy(node *x, node *y) 
{
    if (x == NULL)
    {
        return y;
    }
    else if(y == NULL)
    {
        return x;
    }
    if (x != NULL && y != NULL)
    {
        return x->next = list_copy(x->next,y);
    }

}

Upvotes: 2

Views: 8289

Answers (2)

wildplasser
wildplasser

Reputation: 44240

Non-recursive solution:

node *list_merge(node *x, node *y)
{
node *result= NULL, **pp;
unsigned odd=0;

for (pp = &result; x && y; pp= &(*pp)->next) {
        if (odd++ %2) { *pp = y; y = y->next; }
        else { *pp = x; x = x->next; }
        }
*pp = (x) ? x : y;
return result;
}

Similar, but without the flip-flop variable:

node *list_merge2(node *x, node *y)
{
node *result= NULL, **pp;

for (pp = &result; x || y; ) {
        if (x) { *pp = x; x = x->next; pp= &(*pp)->next; }
        if (y) { *pp = y; y = y->next; pp= &(*pp)->next; }
        }
return result;
}

Upvotes: 1

Jonathan Leffler
Jonathan Leffler

Reputation: 753605

This non-recursive solution works:

#include <stdio.h>

typedef struct list
{
    int data;
    struct list *next;
} node;

static node *list_merge(node *x, node *y)
{
    if (x == 0)
        return y;
    if (y == 0)
        return x;
    node *z = x;
    node *t = x;
    x = x->next;
    while (y != 0 && x != 0)
    {
        t->next = y;
        y = y->next;
        t = t->next;
        t->next = x;
        x = x->next;
        t = t->next;
    }
    if (y != 0)
        t->next = y;
    else if (x != 0)
        t->next = x;
    else
        t->next = 0;
    return z;
}

static void dump_list(char const *tag, node *list)
{
    printf("%s:", tag);
    while (list != 0)
    {
        printf(" -> %d", list->data);
        list = list->next;
    }
    putchar('\n');
}

int main(void)
{
    node list[10] =
    {
        { 1,  &list[1] },
        { 5,  &list[2] },
        { 6,  &list[3] },
        { 3,  &list[4] },
        { 10, &list[5] },
        { 11,       0  },
        {  2, &list[7] },
        {  8, &list[8] },
        {  4, &list[9] },
        {  9,       0  },
    };
    node *x = &list[0];
    dump_list("x", x);
    node *y = &list[6];
    dump_list("y", y);

    node *z = list_merge(x, y);
    dump_list("z", z);
}

Sample run:

x: -> 1 -> 5 -> 6 -> 3 -> 10 -> 11
y: -> 2 -> 8 -> 4 -> 9
z: -> 1 -> 2 -> 5 -> 8 -> 6 -> 4 -> 3 -> 9 -> 10 -> 11

And a recursive solution is:

static node *list_merge(node *x, node *y)
{
    if (x == 0)
        return y;
    if (y == 0)
        return x;
    node *t = list_merge(x->next, y->next);
    node *z = x;
    z->next = y;
    y->next = t;
    return z;
}

Upvotes: 0

Related Questions