合併兩個未排序的鏈接列表？

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