合并两个未排序的链接列表？

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