数据结构单链表的合并

ゞ浴缸里的玫瑰 2022-05-14 05:59 271阅读 0赞

问题：将两个单链表合并

思路：首先用尾插法建立两个链表LA,LB（头插法建立的链表顺序为倒序），遍历LA直到至LA的尾部即LA->next为空，让LA->指向LB的头部然后free(LB)

这是两个链表，LA,LB

![70][]

另LA的尾部指向LB的首部，LA,LB即连接在了一起

![70 1][]

代码：

\#include<iostream>  
\#include<malloc.h>  
using namespace std;  
typedef struct Node  
\{  
    int data;  
    struct Node\*next;  
\}LinkNode,\*Linklist;  
/\*  
    初始化链表   
\*/  
Linklist Initlist()  
\{  
    Linklist L;  
    L=(Linklist)malloc(sizeof(LinkNode));  
    L->next=NULL;  
    return L;  
\}  
/\*  
    尾插法建立链表   
\*/  
void CreatFromTail(Linklist L)  
\{  
    int data=-1;  
    Linklist s,tail;  
    tail=L;  
    cin>>data;  
    while(data!=-1)  
    \{  
        s=(Linklist)malloc(sizeof(LinkNode));  
        s->data=data;  
        tail->next=s;  
        tail=s;  
        cin>>data;  
    \}  
    tail->next=NULL;  
\}  
/\*  
    输出链表   
\*/  
void PrintList(Linklist L)  
\{  
    Linklist p=L->next;  
    while(p)  
    \{  
        cout<<p->data;  
        p=p->next;  
    \}  
\}  
/\*  
    合并链表   
\*/  
void merge(Linklist LA,Linklist LB)  
\{  
    Linklist p=LA->next;  
    while(p->next)  
    \{  
        p=p->next;  
    \}  
    p->next=LB->next;  
    free(LB);  
    //PrintList(LA);  
\}  
int main()  
\{  
    Linklist LA,LB;  
    LA=Initlist();  
    LB=Initlist();  
    CreatFromTail(LA);  
    PrintList(LA);  
    CreatFromTail(LB);  
    PrintList(LB);  
    cout<<endl;  
    merge(LA,LB);  
    PrintList(LA);  
    system("pause");  
    return 0;  
\}

运行结果：

![70 2][]

[70]: /images/20220514/1537cf341a54421d910fe70abcab5cd5.png
[70 1]: /images/20220514/f2d093ead1174062b170eb8625d26ae0.png
[70 2]: /images/20220514/d2669a5ec43a4d25b9ff10acd9ed6a07.png