Question

c语言如何实现两链表合并

不要网上copy的，不用很复杂，越简单越好，叩谢！
设X= (x 1 ,x 2 ,…,x n ) 和Y= (y 1 ,y 2 ,…,y m ) 为两个单链表，试
写出将X 和Y 归并 为一个单链表Z 的算法，使得：
┏ (x 1 ,y 1 ,x 2 ,y 2 ,…,x m ,y m ,x m+1 ,…,x n ) 当m<=n
Z= ┃
┗ (x 1 ,y 1 ,x 2 ,y 2 ,…,x n ,y n ,y n+1 ,…,y m ) 当m>n
这道题谁能答了追五十分！

Answer 1

只要让第一个链表的尾部元素 的 next 指针，指向第二个链表的第一个元素就可以了
如果是双向链表，则除上面操作外，再让第二个链表的 prev指针指向第一个链表最后一个元素

追问

有代码吗，不知道该怎么构建啊

追答

#include<stdio.h>
struct tagS{ tabS * next;}S;
int main()
{
    S* first;
    S* second;
    //.........//其它对链表first 和 second 的操作
    S*p = first;
    while(p->next) p = p->next; //使p定位到链表1的最后一个元素；
    p->next = second;  ///完成两个链表的合并。
   //   ……其它操作
   return 0;
};

追问

有完整的吗(⊙_⊙)？ 举个简单的例子就行(⊙_⊙)

追答

给你的例子不完整吗？

S*p = first;
while(p->next) 
    p = p->next; //使p定位到链表1的最后一个元素；
p->next = second;  ///完成两个链表的合并。

上面的语句是关键。对于单身链表来说合并操作就是让第一个链表的最后一个元素的next指针指向第二个链表的第一个元素。

追问

想要一整段代码，从头到尾的(⊙v⊙)嗯

追答

#include<stdio.h>
#include<malloc.h>

#define SIZE sizeof(tagS)
typedef struct tagS
{
    int id;
    tagS * next;
}S;

S* init(int id)
{
    S *p,* head = NULL;
    int i;
    for(i=0;i<10;i++)
    {
        if( head == NULL)
        {
            head = p = (S *)malloc( SIZE );
            head->id = id++;
        }
        else
        {
            p->next = (S *)malloc( SIZE );
            p = p->next;
            p->id = id++;
        }
    }
    p->next = NULL;
    return head;
}

void output( S*head)
{
    while(head)
    {
        printf("%d => ",head->id);
head = head->next;
    }
    printf("<NUL>\n");
}

int main()
{
    S* first  = init(0); //初始化第一个链表
    S* second = init(100);//初始化第二个链表
   
    //输出第一个链表
    printf("链表1：");
    output( first );

    //输出第二个链表
    printf("链表2：");
    output( second );    
    
    //使p定位到链表1的最后一个元素；
    S*p = first;
    while(p->next) p = p->next; 
    
    ///完成两个链表的合并。
    p->next = second;  
    
    //输出合并后的链表
    printf("合并链表：");
    output( first ); 
    
    getchar();
    return 0;
};