簡介

大家好,這里是jiantaoyab,這篇文章給大家帶來的是鏈表相關的題目練習和解析,希望大家能相互討論進步

---

鏈表的常用技巧

• 畫圖

畫圖能更加清晰,方便我們去理解

• 引入虛擬的頭結點

創建新的頭結點指向原來的鏈表,方便處理邊界情況

• 多定義一個變量

多定義一個next就不用考慮先鏈接誰的問題

• 快慢雙指針

1. 判斷鏈表中是否有環
2. 找環的入口
3. 找鏈表倒數第n個節點

• 鏈表逆序用頭插

兩數相加

https://leetcode.cn/problems/add-two-numbers/

https://leetcode.cn/problems/lMSNwu/ 兩數相加||

原理

代碼

class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* new_head = new ListNode(0); //創建哨兵位頭結點ListNode* tail = new_head;int x = 0;//記錄進位ListNode* cur1 = l1, *cur2 = l2;while(cur1 || cur2 || x){if(cur1){x += cur1->val;cur1 = cur1->next;}if(cur2){x += cur2->val;cur2= cur2->next;}tail->next = new ListNode(x % 10);tail = tail->next;x /= 10;}tail =  new_head->next;delete new_head;return tail;}
};

代碼||

class Solution {
public:ListNode* ReserveList(ListNode* head) {ListNode * head= nullptr;ListNode * curr = head;while(curr) {ListNode* next = curr->next;curr->next = prev;prev = curr;curr = next;}return prev;}ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* new_head = new ListNode(0); //創建哨兵位頭結點ListNode* tail = new_head;int x = 0;//記錄進位l1 = ReserveList(l1);l2 = ReserveList(l2);ListNode* cur1 = l1, *cur2 = l2;while(cur1 || cur2 || x){if(cur1){x += cur1->val;cur1 = cur1->next;}if(cur2){x += cur2->val;cur2= cur2->next;}tail->next = new ListNode(x % 10);tail = tail->next;x /= 10;}tail =  new_head->next;tail = ReserveList(tail);delete new_head;return tail;}
};

兩兩交換鏈表中的節點

https://leetcode.cn/problems/swap-nodes-in-pairs/

代碼

• 遞歸的方式

class Solution {
public:ListNode* swapPairs(ListNode* head) {//終止條件是鏈表只有一個節點 / 鏈表中沒有節點if(head == nullptr || head->next == nullptr) return head;ListNode* nnext =  swapPairs(head->next->next);ListNode* newhead = head->next;newhead->next = head;head->next = nnext;return newhead;}
};

• 迭代的方式

原理

class Solution {
public:ListNode* swapPairs(ListNode* head) {// 0個和1個節點直接返回就好if(head == nullptr || head->next == nullptr)  return head;ListNode* newhead = new ListNode(0); //哨兵位頭結點newhead->next = head;ListNode* prev =newhead;ListNode* cur = prev->next;ListNode* next = cur->next;ListNode* nnext = next->next;while(cur != nullptr && next != nullptr){//交換節點prev->next = next;next ->next = cur;cur ->next = nnext;//更新位置prev = cur;cur = nnext;if(cur != nullptr)next = cur->next;if(next != nullptr)nnext = next->next;}cur = newhead->next;delete newhead;return cur;}
};

重排鏈表(重要)

---

https://leetcode.cn/problems/LGjMqU/

原理

代碼

class Solution {
public:void reorderList(ListNode* head) {// <=2節點的直接返回if(head == nullptr || head->next == nullptr || head->next->next ==nullptr) return ;//1.找到鏈表的中間節點ListNode * slow = head, *fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}//2.將后半部分鏈表逆置ListNode* new_head = new ListNode(0);ListNode* cur = slow->next;     slow->next = nullptr; //斷開鏈表while(cur){ListNode* next = cur->next;cur->next = new_head->next;new_head->next = cur;cur = next;}//3.合并2個鏈表ListNode* ret_head = new ListNode(0);ListNode* prev = ret_head;ListNode* cur1 =head, *cur2 = new_head->next;while(cur1){//先放第一個鏈表prev->next = cur1;cur1 = cur1->next;prev = prev->next;//再放第二個鏈表if(cur2){prev->next = cur2;cur2 = cur2->next;prev = prev->next;}}delete new_head;delete ret_head;}
};

合并 K 個升序鏈表

https://leetcode.cn/problems/vvXgSW/

代碼

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 l :lists){if(l) heap.push(l);}//合并k個有序鏈表ListNode* new_head = new ListNode(0);ListNode* prev = new_head;//小根堆中還有元素說明還有鏈表沒到nullptrwhile(!heap.empty()){ListNode* min = heap.top();heap.pop();prev->next = min;prev = min;if(min->next) heap.push(min->next);}prev->next = nullptr;prev = new_head->next;delete new_head;return prev;}
};//自己用vs調試的時候,可以加上下面代碼調試一步一步看
int main()
{vector<ListNode*> lists = { new ListNode(1, new ListNode(4, new ListNode(5))),new ListNode(1, new ListNode(3, new ListNode(4))),new ListNode(2, new ListNode(6)) };mergeKLists(lists);
}

遞歸代碼

class Solution {
public:ListNode* MergeTowList(ListNode* l ,ListNode* r){if(l == nullptr) return r;if(r == nullptr) return l;ListNode new_head ;new_head.next = nullptr;ListNode* cur1 = l, *cur2 = r, *prev = &new_head ;while(cur1 && cur2){if(cur1->val >= cur2->val){prev = prev->next = cur2;cur2 = cur2->next;}else{prev = prev->next = cur1;cur1 = cur1->next;}}if(cur1) prev->next =cur1;if(cur2) prev->next =cur2;return new_head.next;}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* l = Merge(lists, left, mid); ListNode* r = Merge(lists, mid + 1, right); //合并2個有序鏈表return MergeTowList(l,r);}
public:ListNode* mergeKLists(vector<ListNode*>& lists) {      return Merge(lists, 0, lists.size() - 1);}
};

K 個一組翻轉鏈表

原理

代碼

class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {int N = 0;ListNode * p = head;while(p){p = p->next;N++;}N /= k; //劃分N組ListNode* new_head =  new ListNode(0);ListNode* prev = new_head;ListNode* cur = head;for(int i = 0; i < N; i++){ListNode *first = cur;for(int j = 0; j < k; j++){            ListNode* next = cur->next;cur->next = prev->next;prev->next = cur;cur = next;}prev = first;}//把不需要翻轉的接上prev->next = cur;cur = new_head->next;delete new_head;return cur;}
};