Слияние двух несортированных связанных списков?

Question

Если я начну с структурой:

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

Как бы объединить две из этих структур, позволяет сказать, что эти два X и Y, соответственно, и результирующие называемого Z. Я хочу слияние состоит из x1, указывающих на Y1, указывающий на X2, указывающий на Y2, указывающий на X3 ... пока не будет использован последний Y. Если один список имеет больше, чем другой, просто положите оставшиеся на конец. Наконец, не выделяя память, просто используйте уже используемые узлы (другими словами, просто изменяя указатели каждого элемента, чтобы указать на нужное место). Это то, что я хотел бы, чтобы это выглядело как:

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

прямо сейчас, я пытаюсь рекурсивным через него, но я не могу заставить его работать

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); 
    } 

} 

Answer 1

Это нерекурсивно решение работает:

#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); 
} 

Пример запуска:

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

И рекурсивное решение:

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; 
} 

Answer 2

нерекурсивна решение:

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; 
} 

Аналогично, но без переменной флип-флоп:

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; 
}