算法 ----- 链式
目录
一 、链式
二 、题目
1、两两相加
（1）题目
(3) 代码书写
2、两两交换链表中的节点
（1）题目
（2） 解题思路
（3）代码书写
3、重排链表
（1）题目
（2）解题思路
（3）代码实现
4、合并K个升序链表
（1）题目
（2）解题思路
（3）代码解答
5、K个一组反转链表
（1）题目
（2）解题思路
（3）代码实现
一 、链式
利用链表来解决问题
二 、题目
1、两两相加
（1）题目
(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:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2){ListNode* cur1 = l1;ListNode* cur2 = l2;ListNode* head = new ListNode(0);int t =0; ListNode* pur = head;while(cur1||cur2||t){if(cur1){t+= cur1->val;cur1 = cur1->next;}if(cur2){t+= cur2->val;cur2 = cur2->next;}pur->next = new ListNode(t%10);pur = pur -> next;t/=10;}ListNode* pcur = head -> next;delete head;return pcur;}};2、两两交换链表中的节点
（1）题目
（2） 解题思路
我们也可通过定义四个指针,改变她们的next值来交换结点
边界值为
（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:ListNode* swapPairs(ListNode* head){ListNode* prevhead = new ListNode(0);prevhead -> next = head;if(head == nullptr || head -> next == nullptr){return head;}ListNode* prev = prevhead, *cur = head, *pnext = head -> next, *nnext = pnext->next;while(pnext&&cur){prev->next = pnext;pnext ->next = cur;cur->next = nnext;prev = cur;cur = prev->next;if(nnext)pnext = nnext->next;if (pnext) nnext = pnext ->next;}cur = prevhead ->next;delete prevhead;return cur;}
};3、重排链表
（1）题目
（2）解题思路
1、找到链表的中间
快慢指针
2、逆序后半段的指针（断开两端的指针）
双指针
3、将两端指针链接
双指针
（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) {ListNode *slow = head;ListNode *fast = head;while(fast && fast->next){slow = slow -> next;fast = fast -> next -> next;}ListNode* newhead = new ListNode(0);ListNode *ret = slow -> next;slow -> next = nullptr; while(ret){ListNode *next = ret -> next;ret -> next = newhead -> next;newhead -> next = ret;ret = next; }ListNode* re = new ListNode(0);ListNode *cur1 = head;ListNode *prev = re;ListNode *cur2 = newhead -> next;while(cur1){prev -> next = cur1;prev = prev -> next;cur1 = cur1 -> next;if(cur2){prev->next = cur2;prev = prev -> next;cur2 = cur2 -> next;}}delete newhead;delete re;}
};4、合并K个升序链表
（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
{struct cmp{bool operator()(const ListNode* l1,const ListNode* l2){return l1->val > l2->val;}};
public:ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<ListNode* , vector<ListNode*>, cmp> heap;for(auto e : lists){if(e){heap.push(e);}}ListNode *head = new ListNode(0);ListNode *cur = head;while(!heap.empty()){cur->next = heap.top();cur = cur -> next;heap.pop();if(cur->next)heap.push(cur->next);}cur= head->next;delete head;return cur;}
};思路二解答：
5、K个一组反转链表
（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:ListNode* reverseKGroup(ListNode* head, int k) {int n = 0;ListNode *cur = head;while(cur){cur= cur->next;n++;}n/=k;ListNode* newhead = new ListNode(0);ListNode *prev = newhead;cur = head;for(int j = 0; j < n; j++){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;cur = newhead -> next;delete newhead;return cur;}
};