唐山丰南建设局网站/微信朋友圈广告推广

纸上得来终觉浅，绝知此事要躬行

这篇博客是用来提醒自己，别人的算法，拿来用可以，但自己一定要不看原码实现，并且能够讲出来(我觉得学链表最好的方式就是先画图再写，熟练了之后就不用画了）

目录

1.两个升序链表合并为一个升序链表

算法实现c++: 

2.两个升序链表合并为一个降序链表

整体代码+输出

1.两个升序链表合并为一个升序链表

利用原链表空间，将两个升序的链表合并成一个升序链表，时间复杂度O(N),空间复杂度O(1)

• 用两个指针p1，p2分别遍历L1和L2，用一个尾指针永远指向新链表的最后一个节点
• 比较两个指针指向的节点的大小，将数据域较小的节点用尾插法接在新链表后面
• 尾指针后移，p1或者p2后移
• 当有一个为空时另一个还会有剩余节点没有加入新链表，将剩下的直接接在新链表后面

算法实现c++: 

LinkList mergeTwoLink(LinkList L1,LinkList L2)
{if(L1==NULL||L2==NULL) return L1?L1:L2;LinkList newHead=new LNode();//新建一个头结点 LinkList tail=newHead;//tail为尾指针，指向新链表的最后一个节点 LinkList p1=L1->next;//用p1遍历L1 LinkList p2=L2->next;//用p2遍历L2 while(p1&&p2){if(p1->data<p2->data){//如果p1指向的值小于p2,则用尾插法将p1接在链表尾部 tail->next=p1;//让新链表的尾结点指向p1 p1=p1->next;//更新尾结点 }else{tail->next=p2;p2=p2->next;}tail=tail->next;}tail->next=(p1?p1:p2);return newHead;
}

2.两个升序链表合并为一个降序链表

利用原链表空间，将两个升序链表合并为降序，时间复杂度O(N)，空间复杂度O(1)

•  用两个指针p1，p2分别遍历L1和L2，用指针s每次指向待插入的节点
• 将新链表的头结点的指针域置空
• 开始遍历并用头插法开始插入节点
• 退出循环后对未遍历完的节点用头插法将剩余节点插入新链表

LinkList mergeTwoLinkdesc(LinkList L1,LinkList L2){LinkList p1=L1->next,p2=L2->next,s;//用p1遍历L1，p2遍历L2，s指向每次要插入的节点 LinkList newl=L1;//新链表的头结点用L1的头结点 newl->next=NULL;//将新链表的头节点置空，这样原来的链表就变成了两段 while(p1&&p2){//每次比较两个指针指向的节点的数据域，将较小的那个用头插法查到链表头部 if(p2->data>=p1->data){s=p1;//s指向待插入节点p1 p1=p1->next;//p1指向下一个节点 s->next=newl->next;//将待插入节点接在头节点后面，头插法 newl->next=s;}else{s=p2;p2=p2->next;s->next=newl->next;newl->next=s;}}if(!p1) p1=p2;//处理有一个链表没有全部插入的情况 while(p1){//遍历该链表，用头插法将剩余节点插到新链表中 s=p1;p1=p1->next;s->next=newl->next;newl->next=s;}return newl;
}

整体代码+输出

#include<iostream>
#include<cstdio>
#include<cstring> 
using namespace std;
typedef struct Node{int data;struct Node* next;
}LNode,*LinkList; 
void initLink(LinkList &L){L=new LNode();L->next=NULL;
}
void printLink(LinkList L){LinkList L1=L;if(L1==NULL) return;cout<<L1->data<<" ";printLink(L1->next);
}void createLink(LinkList &L,int n){int x;LinkList p=L;while(n--){cout<<"请输入结点的数据域：";cin>>x;LinkList newNode=new LNode();newNode->next=NULL;newNode->data=x;p->next=newNode;p=p->next;}
}
LinkList mergeTwoLink(LinkList L1,LinkList L2)
{if(L1==NULL||L2==NULL) return L1?L1:L2;LinkList newHead=new LNode();//新建一个头结点 LinkList tail=newHead;//tail为尾指针，指向新链表的最后一个节点 LinkList p1=L1->next;//用p1遍历L1 LinkList p2=L2->next;//用p2遍历L2 while(p1&&p2){if(p1->data<p2->data){//如果p1指向的值小于p2,则用尾插法将p1接在链表尾部 tail->next=p1;//让新链表的尾结点指向p1 p1=p1->next;//更新尾结点 }else{tail->next=p2;p2=p2->next;}tail=tail->next;}tail->next=(p1?p1:p2);return newHead;
}
int main()
{LinkList L1,L2;initLink(L1);initLink(L2);createLink(L1,3);cout<<"输出链表一：";printLink(L1);cout<<endl;createLink(L2,3);cout<<"输出链表二：";printLink(L2);cout<<endl;LinkList L=mergeTwoLink(L1,L2);cout<<"升序合并两个链表：";printLink(L);return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring> 
using namespace std;
typedef struct Node{int data;struct Node* next;
}LNode,*LinkList; 
void initLink(LinkList &L){L=new LNode();L->next=NULL;
}
void printLink(LinkList L){LinkList L1=L;if(L1==NULL) return;cout<<L1->data<<" ";printLink(L1->next);
}void createLink(LinkList &L,int n){int x;LinkList p=L;while(n--){cout<<"请输入结点的数据域：";cin>>x;LinkList newNode=new LNode();newNode->next=NULL;newNode->data=x;p->next=newNode;p=p->next;}
}
LinkList mergeTwoLinkdesc(LinkList L1,LinkList L2){LinkList p1=L1->next,p2=L2->next,s;//用p1遍历L1，p2遍历L2，s指向每次要插入的节点 LinkList newl=L1;//新链表的头结点用L1的头结点 newl->next=NULL;//将新链表的头节点置空，这样原来的链表就变成了两段 while(p1&&p2){//每次比较两个指针指向的节点的数据域，将较小的那个用头插法查到链表头部 if(p2->data>=p1->data){s=p1;//s指向待插入节点p1 p1=p1->next;//p1指向下一个节点 s->next=newl->next;//将待插入节点接在头节点后面，头插法 newl->next=s;}else{s=p2;p2=p2->next;s->next=newl->next;newl->next=s;}}if(!p1) p1=p2;//处理有一个链表没有全部插入的情况 while(p1){//遍历该链表，用头插法将剩余节点插到新链表中 s=p1;p1=p1->next;s->next=newl->next;newl->next=s;}return newl;
}
int main()
{LinkList L1,L2;initLink(L1);initLink(L2);createLink(L1,3);cout<<"输出链表一：";printLink(L1);cout<<endl;createLink(L2,3);cout<<"输出链表二：";printLink(L2);cout<<endl;LinkList LL=mergeTwoLinkdesc(L1,L2);cout<<"降序合并两个链表：";printLink(LL);return 0;
}