目录
一、思路
二、代码
三、测试
四、总结
一、思路
两个链表中对应位置的结点进行比较，较小的插入到一个新的链表里
1.如果A链表到达尾结点，B链表没有到达尾结点，那么直接将B链表剩余结点插入到新链表中
2.如果B链表到达尾结点，A链表没有到达尾结点，那么直接将A链表剩余结点插入到新链表中
二、代码
#include<iostream>
#include "malloc.h"
using namespace std;
typedef struct LNode {
int data;
struct LNode * next;
}LNode, *LinkList ;
int tail_create_heahLinked_List(LinkList & L,int n)
{
if( n <= 0)
return 1;
LinkList head = (LinkList)malloc(sizeof(LNode));//头结点的存储地址
if(NULL == head) return 1; //分配空间失败
L = head; //头指针L存储头结点P的地址，即头指针指向头结点
L->data = 0; //用头结点统计元素个数，刚开始为0个
L->next = NULL; //此时链表为空
LinkList temp = L;
for(int i = 0;i<n;i++)
{
LinkList List_Node = (LinkList)malloc(sizeof(LNode));
scanf("%d",&List_Node->data);
L->data++;
List_Node->next = NULL; //每插入一个元素，头结点统计链表元素个数加一
temp->next = List_Node; //尾插法，即链表中的元素顺序与输入相同
temp = temp->next;
if(i == n-1 ){
temp->next = NULL;
}
}
return 0;
}
void headlinked_List_Traverse(LinkList L)
{
cout<<"合并后链表为:"<<endl;
LinkList p = L;
while(p != NULL)
{
cout<<p->data<<" ";
p = p->next;
}
cout<<endl;
}
int destroy_linked_list(LinkList L)
{
LinkList p = NULL;
while(L)
{
p = L->next;
free(L);
L = p;
}
cout<<"销毁链表成功"<<endl;
return 0;
}
LinkList Merge_Sorted_LinkList(LinkList List_A,LinkList List_B)
{
if(NULL == List_A )
return List_B;
if( NULL == List_B)
return List_A;
LinkList pMergedHead = NULL;
if(List_A->data < List_B->data)
{
pMergedHead = List_A;
pMergedHead->next = Merge_Sorted_LinkList(List_A->next,List_B);
}
else
{
pMergedHead = List_B;
pMergedHead->next = Merge_Sorted_LinkList(List_A,List_B->next);
}
return pMergedHead;
}
int main()
{
int length_A,length_B;
cin>>length_A;
cin>>length_B;
LinkList List_A = NULL;
LinkList List_B = NULL;
LinkList List_C = NULL;//合并后的链表
tail_create_heahLinked_List(List_A,length_A);
while((getchar()) !='\n');//清空缓冲区
tail_create_heahLinked_List(List_B,length_B);
List_C = Merge_Sorted_LinkList(List_A->next,List_B->next);
headlinked_List_Traverse(List_C);
destroy_linked_list(List_C);
return 0;
}
三、测试
1 2
-1
-2 3
合并后链表为:
-2 -1 3
销毁链表成功
————————————
3 4
-1 2 4
0 1 4 8
合并后链表为:
-1 0 1 2 4 4 8
销毁链表成功
四、总结
这里用到了递归，另外用链表很高效，因为两个链表是有序的，当某一个到达尾结点，可以直接将另一个链表的结点连接到新链表
