鏈表

合并兩個有序鏈表

https://leetcode.cn/problems/merge-two-sorted-lists/

1.定義一個哨兵位節點和一個tail節點標志尾節點

2.遍歷兩條有序鏈表，誰小就鏈接誰

3.最后還剩一條鏈表是沒有遍歷完成的，那么就讓tail節點鏈接它

class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {//1.新建哨兵位節點ListNode*　phead = new ListNode(-1);ListNode* tail = phead;//2.誰小就鏈接誰while(list1 && list2){if(list1->val > list2->val){tail->next = list2;tail = list2;list2 = list2->next;}else {tail->next = list1;tail = list1;list1 = list1->next;}}//3.判斷誰還沒有鏈接完if(list1) tail->next = list1;if(list2) tail->next = list2;return phead->next;}
};

---

反轉鏈表

https://leetcode.cn/problems/reverse-linked-list/description/

prev：記錄前一個節點 cur：當前遍歷到的節點 next：保存cur的下一個節點

• 先保存下一個節點 然后更改cur的指向，指向前一個節點
• 然后迭代往后走

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* prev = nullptr;//記錄前一個節點ListNode* cur = head;//記錄當前節點ListNode* next = nullptr;//記錄下一個節點while(cur){next = cur->next;//先保存下一個節點cur->next = prev;//更改當前節點指向//prev cur next 迭代往后走prev = cur;cur = next;}return prev;}
};

---

復制帶隨機指針的鏈表

https://leetcode.cn/problems/copy-list-with-random-pointer/

1.在原鏈表節點之后拷貝一個節點

2.處理拷貝節點的random指針

• 注意：拷貝節點的random指針指向的節點是其原鏈表節點的random指針指向的節點的下一個節點
• 坑點：有可能cur->random是空，也就是原來節點的random指針為空，那么當前拷貝節點的random指針也應該為空，否則cur->random->next 就會對空指針解引用！

3.分離兩條鏈表

• 最好定義一個哨兵位節點和一個tail指針用于標記鏈接拷貝鏈表，
• cur CopyCur next三者的關系重新處理

class Solution {public:Node* copyRandomList(Node* head) {if(head == nullptr ) return nullptr;//1.在原節點后面copy一個節點Node* cur = head;while(cur){Node* copy = new Node(cur->val);//拷貝節點Node* next = cur->next;//cur copy next 鏈接cur->next = copy;copy->next = next;cur = next;//繼續復制下一個節點}//2.處理拷貝節點的random指針cur = head;while(cur){Node*　curCopy = cur->next;//cur的拷貝節點curCopy->random = cur->random == nullptr?nullptr:cur->random->next;cur = curCopy->next;}//3.拆離拷貝鏈表cur = head;Node* pnewHead = new Node(-1);//哨兵位Node* tail = pnewHead;while(cur){//cur copyCur next  Node* copyCur = cur->next;Node* next = copyCur->next;copyCur->next = nullptr;//讓拷貝節點獨立存在tail->next = copyCur;tail = tail->next;//重新處理鏈接關系,向后走cur->next = next;cur = next;}return pnewHead->next;}
};

---

環形鏈表

https://leetcode.cn/problems/linked-list-cycle/description/

方法：使用快慢指針，二者從頭開始走，一個一次走兩步，一個一次走一步，當二者相遇的時候，說明有環

class Solution {
public:bool hasCycle(ListNode *head) {//鏈表為空//注意:一個節點也能成環！ 自己指向自己if(!head) return false;//快慢指針ListNode* fast = head;ListNode* slow = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;//二者相遇  注意:該條件不能放在上面！！！因為最初fast和slow都指向head,該條件應該放在下面if(slow == fast) return true;}return false;}
};

延申1：fast一次走兩步,slow一次走一步,為什么一定能相遇？會不會在環里錯過,永遠遇不上

結論：slow一次走一步，fast一次走兩步，如果存在環,slow和fast一定會在環內相遇

1.slow和fast，如果有環，一定是fast先進環，這時slow走了入環前距離的一半

2.隨著slow進環，fast已經在環里面走了一段距離了（距離的多少跟環的大小有關）

• 假設slow進環的時候，slow和fast的距離為N，fast開始追趕slow

3.slow一次走一步，fast一次走兩步，二者的距離變化為：N N- 1 N -2 … 0，當二者的距離變為0的時候，就是相遇了

延申2：fast一次走n步(n>2)，slow一次走一步，fast和slow能相遇嗎

結論：fast一次走n步(n>2)，slow一次走一步，不一定會相遇

• 假設有環，fast一次走n步，slow一次走1步，fast和slow的距離不斷減少n-1步

例子：假設fast一次走3步，如果slow進環之后，slow和fast的距離為N

如果N為偶數，那么二者之間的距離變化為：N N - 2 N - 4 … 2 0，此時二者相遇

如果N為計數，那么二者之間的距離變化為：N N - 2 N - 4 … 1 -1 ，二者距離變為-1，意味著fast超越了slow，此時fast和slow的距離為C -1 (假設C為環的大小)

• 如果C - 1 為偶數，那么下一輪fast可以追上slow，二者相遇
• 如果C - 1 為奇數，那么二者永遠追不上

---

環形鏈表II

https://leetcode.cn/problems/linked-list-cycle-ii/description/

做法：

1.先看是否有環，快慢指針，fast一次走兩步，slow一次走一步，如果存在環，fast和slow一定會相遇

2.假設相遇點為meetnode，一個指針從鏈表的頭開始走，一個指針從相遇點開始走，二者一次走一步，當二者相遇的時候，該位置就是入環節點

class Solution {
public:ListNode *detectCycle(ListNode *head) {if(!head) return nullptr;//快慢指針ListNode* fast = head;ListNode* slow = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;//二者相遇  注意:該條件不能放在上面！！！因為最初fast和slow都指向head,該條件應該放在下面if(slow == fast) {//分別從相遇點和鏈表頭開始走,一次走一步  此時相遇就是入環位置ListNode*　meet = slow;slow = head;while(slow != meet) {slow = slow->next;meet = meet->next;}return meet;}}return nullptr; //沒有環}
};

---

相交鏈表

https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

方法1：將A鏈表的所有節點放到容器當中（要放地址，不能放值），然后遍歷B鏈表，看能否在容器當中找到該元素，如果找到，那么該節點就是相交節點

class Solution {
public://方法1：用容器保存其中一個鏈表的節點,然后遍歷另外一個鏈表進行比對ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {multiset<ListNode*> s;ListNode* cur = headA;while(cur) {s.insert(cur);cur = cur->next;}cur = headB;while(cur){cout << cur->val << endl;if(s.find(cur) != s.end()) return cur;cur = cur->next;}return nullptr;//不相交}
};

---

方法2：A中的每個結點和B分別比較(B和A比較也可以)，看二者的地址是否一致 - O(N*M)

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode* curA = headA;ListNode* curB = headB;while(curA) //確定一個A節點{curB = headB;while(curB)//遍歷整條B鏈表{if(curA == curB){return curA;}curB = curB ->next;}curA = curA->next;}return nullptr;}
};

方法3：

1.先統計兩條鏈表的長度，假設二者長度差距為gap

2.長鏈表先往后走gap步，然后長短鏈表一起往后走，如果相遇，那么就是相交節點

class Solution {public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if(!headA || !headB) return nullptr;//1.統計兩條鏈表的長度int lenA = 0;int lenB = 0;ListNode* cur = headA;while(cur)  lenA++,cur = cur->next;cur = headB;