鏈表

合并兩個(gè)有序鏈表

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

1.定義一個(gè)哨兵位節(jié)點(diǎn)和一個(gè)tail節(jié)點(diǎn)標(biāo)志尾節(jié)點(diǎn)

2.遍歷兩條有序鏈表，誰(shuí)小就鏈接誰(shuí)

3.最后還剩一條鏈表是沒(méi)有遍歷完成的，那么就讓tail節(jié)點(diǎn)鏈接它

class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {//1.新建哨兵位節(jié)點(diǎn)ListNode*　phead = new ListNode(-1);ListNode* tail = phead;//2.誰(shuí)小就鏈接誰(shuí)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.判斷誰(shuí)還沒(méi)有鏈接完if(list1) tail->next = list1;if(list2) tail->next = list2;return phead->next;}
};

---

反轉(zhuǎn)鏈表

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

prev：記錄前一個(gè)節(jié)點(diǎn) cur：當(dāng)前遍歷到的節(jié)點(diǎn) next：保存cur的下一個(gè)節(jié)點(diǎn)

• 先保存下一個(gè)節(jié)點(diǎn) 然后更改cur的指向，指向前一個(gè)節(jié)點(diǎn)
• 然后迭代往后走

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

---

復(fù)制帶隨機(jī)指針的鏈表

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

1.在原鏈表節(jié)點(diǎn)之后拷貝一個(gè)節(jié)點(diǎn)

2.處理拷貝節(jié)點(diǎn)的random指針

• 注意：拷貝節(jié)點(diǎn)的random指針指向的節(jié)點(diǎn)是其原鏈表節(jié)點(diǎn)的random指針指向的節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
• 坑點(diǎn)：有可能cur->random是空，也就是原來(lái)節(jié)點(diǎn)的random指針為空，那么當(dāng)前拷貝節(jié)點(diǎn)的random指針也應(yīng)該為空，否則cur->random->next 就會(huì)對(duì)空指針解引用！

3.分離兩條鏈表

• 最好定義一個(gè)哨兵位節(jié)點(diǎn)和一個(gè)tail指針用于標(biāo)記鏈接拷貝鏈表，
• cur CopyCur next三者的關(guān)系重新處理

class Solution {public:Node* copyRandomList(Node* head) {if(head == nullptr ) return nullptr;//1.在原節(jié)點(diǎn)后面copy一個(gè)節(jié)點(diǎn)Node* cur = head;while(cur){Node* copy = new Node(cur->val);//拷貝節(jié)點(diǎn)Node* next = cur->next;//cur copy next 鏈接cur->next = copy;copy->next = next;cur = next;//繼續(xù)復(fù)制下一個(gè)節(jié)點(diǎn)}//2.處理拷貝節(jié)點(diǎn)的random指針cur = head;while(cur){Node*　curCopy = cur->next;//cur的拷貝節(jié)點(diǎn)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;//讓拷貝節(jié)點(diǎn)獨(dú)立存在tail->next = copyCur;tail = tail->next;//重新處理鏈接關(guān)系,向后走cur->next = next;cur = next;}return pnewHead->next;}
};

---

環(huán)形鏈表

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

方法：使用快慢指針，二者從頭開(kāi)始走，一個(gè)一次走兩步，一個(gè)一次走一步，當(dāng)二者相遇的時(shí)候，說(shuō)明有環(huán)

class Solution {
public:bool hasCycle(ListNode *head) {//鏈表為空//注意:一個(gè)節(jié)點(diǎn)也能成環(huán)！ 自己指向自己if(!head) return false;//快慢指針ListNode* fast = head;ListNode* slow = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;//二者相遇  注意:該條件不能放在上面！?。∫?yàn)樽畛鮢ast和slow都指向head,該條件應(yīng)該放在下面if(slow == fast) return true;}return false;}
};

延申1：fast一次走兩步,slow一次走一步,為什么一定能相遇？會(huì)不會(huì)在環(huán)里錯(cuò)過(guò),永遠(yuǎn)遇不上

結(jié)論：slow一次走一步，fast一次走兩步，如果存在環(huán),slow和fast一定會(huì)在環(huán)內(nèi)相遇

1.slow和fast，如果有環(huán)，一定是fast先進(jìn)環(huán)，這時(shí)slow走了入環(huán)前距離的一半

2.隨著slow進(jìn)環(huán)，fast已經(jīng)在環(huán)里面走了一段距離了（距離的多少跟環(huán)的大小有關(guān)）

• 假設(shè)slow進(jìn)環(huán)的時(shí)候，slow和fast的距離為N，fast開(kāi)始追趕slow

3.slow一次走一步，fast一次走兩步，二者的距離變化為：N N- 1 N -2 … 0，當(dāng)二者的距離變?yōu)?的時(shí)候，就是相遇了

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

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

• 假設(shè)有環(huán)，fast一次走n步，slow一次走1步，fast和slow的距離不斷減少n-1步

例子：假設(shè)fast一次走3步，如果slow進(jìn)環(huán)之后，slow和fast的距離為N

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

如果N為計(jì)數(shù)，那么二者之間的距離變化為：N N - 2 N - 4 … 1 -1 ，二者距離變?yōu)?1，意味著fast超越了slow，此時(shí)fast和slow的距離為C -1 (假設(shè)C為環(huán)的大小)

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

---

環(huán)形鏈表II

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

做法：

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

2.假設(shè)相遇點(diǎn)為meetnode，一個(gè)指針從鏈表的頭開(kāi)始走，一個(gè)指針從相遇點(diǎn)開(kāi)始走，二者一次走一步，當(dāng)二者相遇的時(shí)候，該位置就是入環(huán)節(jié)點(diǎn)

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;//二者相遇  注意:該條件不能放在上面?。。∫?yàn)樽畛鮢ast和slow都指向head,該條件應(yīng)該放在下面if(slow == fast) {//分別從相遇點(diǎn)和鏈表頭開(kāi)始走,一次走一步  此時(shí)相遇就是入環(huán)位置ListNode*　meet = slow;slow = head;while(slow != meet) {slow = slow->next;meet = meet->next;}return meet;}}return nullptr; //沒(méi)有環(huán)}
};

---

相交鏈表

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

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

class Solution {
public://方法1：用容器保存其中一個(gè)鏈表的節(jié)點(diǎn),然后遍歷另外一個(gè)鏈表進(jìn)行比對(duì)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中的每個(gè)結(jié)點(diǎn)和B分別比較(B和A比較也可以)，看二者的地址是否一致 - O(N*M)

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

方法3：

1.先統(tǒng)計(jì)兩條鏈表的長(zhǎng)度，假設(shè)二者長(zhǎng)度差距為gap

2.長(zhǎng)鏈表先往后走gap步，然后長(zhǎng)短鏈表一起往后走，如果相遇，那么就是相交節(jié)點(diǎn)

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