优选算法——链表

 💁‍♂️个人主页：进击的荆棘

👇作者其它专栏：

《数据结构与算法》《算法》《C++起始之路》

相关题解

1.两数相加

算法思路（模拟）：

两个链表都是逆序存储数字的，即两个链表的个位数、十位数等都已经对应，可以直接相加。在相加过程中，我们要注意是否产生进位，产生进位时需要将进位和链表数字一同相加。若产生进位的位置在链表底部，即答案位数比原链表位数长一位，还需要再new一个结点存储最高位。

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* cur1=l1,*cur2=l2; ListNode* newhead=new ListNode(0);//虚拟头结点 ListNode* head=newhead;//尾指针 int t=0;//记录进位 //t中可能还保存一个进位 while(cur1||cur2||t){ if(cur1){ t+=cur1->val; cur1=cur1->next; } if(cur2){ t+=cur2->val; cur2=cur2->next; } ListNode* tmp=new ListNode(t%10); head->next=tmp; head=head->next; t/=10; } head=newhead->next; delete newhead; return head; } };

2.两两交换链表中的节点

算法思路（模拟）：

由画图就可以明白。

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* swapPairs(ListNode* head) { if(!head||!head->next) return head; ListNode* newhead=new ListNode(0,head); ListNode* prev=newhead,*cur=newhead->next,*next=cur->next,*nnext=cur->next->next; while(cur&&next){ //交换结点 prev->next=next; cur->next=nnext; next->next=cur; //为修改下一对结点做准备 prev=cur; cur=nnext; if(cur) next=cur->next; if(next) nnext=next->next; } head=newhead->next; delete newhead; return head; } };

3.重排链表

算法思路：

1.找中间节点，分成两个链表

2.将第二条链表逆序

3.合并两条链表

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: void reorderList(ListNode* head) { if(!head||!head->next||!head->next->next) return ; ListNode* slow=head,*fast=head; //找到中间结点，将链表断开 while(fast&&fast->next){ slow=slow->next; fast=fast->next->next; } ListNode* head2=new ListNode(0); ListNode* cur=slow->next; slow->next=nullptr; //反转第二条链表，头插 while(cur){ //保存下一结点，防止找不到 ListNode* next=cur->next; cur->next=head2->next; head2->next=cur; cur=next; } //合并两条链表 ListNode* ret=new ListNode(0); ListNode* prev=ret; ListNode* cur1=head,*cur2=head2->next; while(cur1){ prev->next=cur1; prev=prev->next; cur1=cur1->next; if(cur2){ prev->next=cur2; cur2=cur2->next; prev=prev->next; } } delete head2; delete ret; } };

4.合并 K 个升序链表

算法思路一（堆）：

合并两个有序列表是比较简单且做过的，就是用双指针依次比较链表1、链表2为排序的最小元素，选择更小的那一个加入有序的答案链表中。

合并k个升序链表时，我们依旧可以选择k个链表中，头节点最小的那一个。可以用堆这个数据结构，我们可以将所有的头节点放进一个小根堆中，这样就能快速找到每次k个链表中，最小的元素是哪个。

算法思路二（递归）：

逐一比较时，答案链表越来越长，每个跟它合并的小链表的元素都需要比较很多次才可以成功排序。比如，我们有8个链表，每个链表长100。

逐一合并时，我们合并链表的长度分别为（0，100），（100，100），（200，100）（300，100），（400，100），（500，100），（600，100），（700，100）。所有链表的总长度共计3600。

若尽可能让长度相同发链表进行两两合并呢？这是合并链表的长度分别是（100，100）x4，（200，200）x2，（400，400），共计2400。比上一种的计算量整整少了1/3。

算法流程：

1.特例，若题目给出空链表，无需合并，直接返回；

2.返回递归结果。

递归函数设计：

1.递归出口：若当前要合并的链表编号范围左右值相等，无需合并，直接返回当前链表；

2.用二分思想，等额划分左右两段需要合并的链表，使这两段合并后的长度尽可能相等；

3.对左右两段分别递归，合并[l,r]范围内的链表；

4.再调用mergeTwoLists函数进行合并（就是合并两个有序链表）

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ //利用优先级队列的思想，建堆 struct cmp{ bool operator()(ListNode* l1,ListNode* l2){ return l1->val>l2->val; } }; class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { //创建优先级队列，建小堆 priority_queue<ListNode*,vector<ListNode*>,cmp> heap; //将所有链表的头结点入队列 for(auto l:lists){ if(l) heap.push(l); } ListNode* head=new ListNode(0); ListNode* prev=head; while(!heap.empty()){ //一直取堆顶 ListNode* t=heap.top(); heap.pop(); prev=prev->next=t; //若链表中还有结点，向后移动 if(t->next) {t=t->next;heap.push(t);} } prev=head->next; delete head; return prev; } }; //法三：分治——递归，时间复杂度O(n*k*logk) class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { return merge(lists,0,lists.size()-1); } ListNode* merge(vector<ListNode*>& lists,int left,int right){ if(left>right) return nullptr; //只有一条链表的情况 if(left==right) return lists[left]; //将数组分为两块 int mid=(left+right)>>1; ListNode* l1=merge(lists,left,mid); ListNode* l2=merge(lists,mid+1,right); //合并两个有序数组 return mergeTosort(l1,l2); } ListNode* mergeTosort(ListNode* l1,ListNode* l2){ if(!l1) return l2; if(!l2) return l1; ListNode* cur1=l1,*cur2=l2; ListNode head; ListNode* prev=&head; head.next=nullptr; while(cur1&&cur2){ if(cur1->val <= cur2->val){ prev=prev->next=cur1; cur1=cur1->next; } else{ prev=prev->next=cur2; cur2=cur2->next; } } if(cur1) prev->next=cur1; if(cur2) prev->next=cur2; return head.next; } };

5.K 个一组翻转链表

我们可以把链表按k个为一组进行分组，组内进行反转，并且记录反转后的头尾节点，使其可以和前、后连接起来。

可以先求出一共需要逆序多少组（假设逆序n组），然后重复n次长度为k的链表的逆序即可。

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { int n=0; ListNode* cur=head; while(cur){ n++; cur=cur->next; } //求出需要翻转多少组 n/=k; ListNode* newhead=new ListNode(0); ListNode* prev=newhead; cur=head; while(n--){ ListNode* tmp=cur; for(int i=0;i<k;i++){ ListNode* next=cur->next; cur->next=prev->next; prev->next=cur; cur=next; } prev=tmp; } prev->next=cur; prev=newhead->next; delete newhead; return prev; } };