算法9--链表

链表

- 原理
- 经典例题
- [2. 两数相加](https://leetcode.cn/problems/add-two-numbers/description/)
- [24. 两两交换链表中的节点](https://leetcode.cn/problems/swap-nodes-in-pairs/)
- [143. 重排链表](https://leetcode.cn/problems/reorder-list/description/)
- [23. 合并 K 个升序链表](https://leetcode.cn/problems/merge-k-sorted-lists/description/)
- [25. K 个一组翻转链表](https://leetcode.cn/problems/reverse-nodes-in-k-group/description/)

原理

链表相关的题目就是根据题意堆链表进行增删查改，技巧：

我们可以为链表添加一个表头，以方便我们处理边界细节问题。
如果想要逆序某个链表，只需要遍历该链表进行一次头插即可。
找链表的中间节点只需要一次快慢指针遍历即可。

经典例题

2. 两数相加

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
{struct ListNode*ret=NULL;struct ListNode*cur=NULL;int add=0;while(l1&&l2){int sum=l1->val+l2->val;if(!ret){ret=(struct ListNode*)malloc(sizeof(struct ListNode));cur=ret;}else{cur->next=(struct ListNode*)malloc(sizeof(struct ListNode));cur=cur->next;}cur->val=(sum+add)%10;add=(sum+add)/10;cur->next=NULL;l1=l1->next;l2=l2->next;}while(l1){cur->next=(struct ListNode*)malloc(sizeof(struct ListNode));cur=cur->next;cur->next=NULL;cur->val=(add+l1->val)%10;add=(add+l1->val)/10;l1=l1->next;}while(l2){cur->next=(struct ListNode*)malloc(sizeof(struct ListNode));cur=cur->next;cur->next=NULL;cur->val=(add+l2->val)%10;add=(add+l2->val)/10;l2=l2->next;}while(add){cur->next=(struct ListNode*)malloc(sizeof(struct ListNode));cur=cur->next;cur->next=NULL;cur->val=add%10;add/=10;}return ret;
}

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

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

/*** 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(nullptr==head||nullptr==head->next){return head;}ListNode newHead;ListNode* cur1=head;ListNode* cur2=head->next;ListNode* pre=&newHead;while(cur1&&cur2){cur1->next=cur2->next;cur2->next=cur1;pre->next=cur2;pre=cur1;cur1=cur1->next;if(cur1){cur2=cur1->next;}}return newHead.next;}
};

143. 重排链表

给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 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:void reorderList(ListNode* head) {if(nullptr==head||nullptr==head->next){return;}ListNode* cur1=head;ListNode* cur2=head->next;while(cur2){cur2=cur2->next;if(nullptr==cur2){break;}cur2=cur2->next;cur1=cur1->next;}ListNode* head1=head;ListNode* head2=cur1->next;cur1->next=nullptr;//反转链表2cur1=head2;cur2=head2->next;ListNode* t=head2;while(cur1&&cur2){ListNode* tmp=cur2->next;cur2->next=cur1;cur1=cur2;head2=cur2;cur2=tmp;}t->next=nullptr;cur1=head1;cur2=head2;while(cur1&&cur2){ListNode* tmp1=cur1->next;ListNode* tmp2=cur2->next;cur1->next=cur2;cur2->next=tmp1;cur1=tmp1;cur2=tmp2;}}
};

23. 合并 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* _mergeList(ListNode* list1,ListNode* list2){ListNode t;ListNode* head=&t;head->next=nullptr;ListNode* cur=head;ListNode* cur1=list1;ListNode* cur2=list2;while(cur1&&cur2){if(cur1->val<cur2->val){cur->next=cur1;cur1=cur1->next;cur=cur->next;}else if(cur1->val>cur2->val){cur->next=cur2;cur2=cur2->next;cur=cur->next;}else{cur->next=cur1;cur1=cur1->next;cur=cur->next;cur->next=cur2;cur2=cur2->next;cur=cur->next;}}if(cur1){cur->next=cur1;}if(cur2){cur->next=cur2;}return head->next;}ListNode* mergeKLists(vector<ListNode*>& lists) {if(0==lists.size())    {return nullptr;}if(1==lists.size()){return lists[0];}ListNode* head=lists[0];int i=1;while(i<lists.size()){head=_mergeList(head,lists[i++]);}return head;}
};

25. K 个一组翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 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:void reverse(ListNode* head,ListNode* tail){ListNode* pre=head;ListNode* cur=head->next;while(pre!=tail){ListNode* tmp=cur->next;cur->next=pre;pre=cur;cur=tmp;}head->next=nullptr;}ListNode* reverseKGroup(ListNode* head, int k) {ListNode t;ListNode* nhead=&t;nhead->next=head;ListNode* prehead=nhead;ListNode* cur=head;ListNode* thead=head;ListNode* ttail=head;int i=k;while(cur){--i;ttail=cur;cur=cur->next;if(0==i){reverse(thead,ttail);prehead->next=ttail;prehead=thead;thead=cur;prehead->next=thead;i=k;}}return nhead->next;}
};