目錄

一 、鏈式

二 、題目

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;}
};