24、兩兩交換鏈表中的節點

·模擬節點交換

題目鏈接：https://leetcode.cn/problems/swap-nodes-in-pairs/

思路：回圈中兩兩交換
???手寫模擬一下交換的程序就比較容易了
???下圖是我寫的模擬程序：

?
代碼實作：中規中矩地模擬就完事
?????時間復雜度O(n)
?????空間復雜度O(1)

/**
 * 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* cur =head;
        ListNode* per =new ListNode();
        ListNode* k = new ListNode();
        bool t=false;
        while(cur!=nullptr&&cur->next!=nullptr){//有可以進行交換的節點
            k=cur->next;//per要指向cur->next,先用k存cur->next
            cur->next=k->next;//改變cur的指標域
            per->next=k;
            per=per->next;
            per->next=cur;
            if(!t){//注意，當頭兩個節點進行交換后，head也需要進行交換
                head=per;
                t=true;
            }
            per=cur;
            cur=cur->next;          
        }
        return head;
    }
};

識訓摘要：carl哥的方法用了虛擬頭節點，我沒用虛擬頭節點，寫下來還比較順暢，就是要注意回傳的head因為交換，要改變，

學習的文章鏈接：https://programmercarl.com/0024.兩兩交換鏈表中的節點.html#_24-兩兩交換鏈表中的節點

19、洗掉鏈表的倒數第N個節點

·鏈表長度計算，雙指標更快

單鏈表倒著數真是吃飽沒事干，正著數再減一減就可以了

題目鏈接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

思路：先計算鏈表的總長度
???然后算出正著數是第幾個
???洗掉節點

代碼實作：
?????時間復雜度O(n)
?????空間復雜度O(1)

/**
 * 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* removeNthFromEnd(ListNode* head, int n) {
        int m=1;//計數器
        ListNode* phead=new ListNode(0,head);//虛擬頭節點
        ListNode* cur=phead->next;
        while(cur->next!=nullptr){//計算鏈表長度
            cur=cur->next;
            m++;
        }
        m=m-n;//從左至右第m個
        cur=phead;
        while(m>0){
            cur=cur->next;
            m--;
        }
        ListNode* d=cur->next;
        cur->next=cur->next->next;
        delete d;
        return phead->next;
    }
};

識訓摘要：設定虛擬頭節點方便處理針對頭節點的情況，
?????比如刪掉頭節點后，就不能回傳頭節點，
?????但是可以回傳虛擬頭節點的指標域doge

?????此題用雙指標法可以只掃一遍鏈表，類似于滑塊doge
?????雙指標yyds！精簡了計算666
?????ps：雙指標的代碼可以在文章鏈接里參考，就不ctrl+v了哈哈哈
?????復習的時候可以用雙指標實作

學習的文章鏈接：https://programmercarl.com/0019.洗掉鏈表的倒數第N個節點.html#_19-洗掉鏈表的倒數第n個節點

面試題02.07.鏈表相交

·世界線收束doge

就是說收束前兩條鏈表不一樣長~

題目鏈接：https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/

前提：不存在環
???相交點不是數值相等，而是指標(節點)相等

思路：算出兩條鏈表的長度
???兩條鏈表相交節點之后的長度相等
???進行一個右對齊的操作，然后往后找相交節點

代碼實作：
?????時間復雜度O(n)
?????空間復雜度O(1)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* curA=new ListNode(0,headA);
        ListNode* curB=new ListNode(0,headB);
        int la=0;
        int lb=0;
        int l;
        while(curA->next!=NULL){
            curA=curA->next;
            la++;
        }
        curA=headA;
        while(curB->next!=NULL){
            curB=curB->next;
            lb++;
        }
        curB=headB;
        l=(la>lb)?la:lb;
        for(int i=1;i<=l;i++){
            if(curA==curB){
                return curA;
            }
            else if(la>lb){
                curA=curA->next;
                la--;
            }
            else if(la<lb){
                curB=curB->next;
                lb--;
            }
            else{
                curA=curA->next;
                curB=curB->next;
            }
        }
        return NULL;
    }
};

識訓摘要：虛擬頭節點方便考慮頭節點的情況（梅開n度），
?????鏈表長度不一樣就把它拉到一樣，然后就一路暢通了，

學習的文章鏈接：https://programmercarl.com/面試題02.07.鏈表相交.html#思路

142、環形鏈表Ⅱ

·雙指標+一些數學運算

他跑、她走，她被追~此處應有bgm：戀愛回圈doge

題目鏈接：https://leetcode.cn/problems/linked-list-cycle-ii/

思路：雙指標，一快一慢
???每次快指標比慢指標還要快一步 (just one)
???快指標先進入回圈（回圈ing）
???直到兩個指標相遇（！！）
???經過一些數學運算
???請回傳：回圈入口

代碼實作：
?????時間復雜度O(n)
?????空間復雜度O(1)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        int xy=0;
        ListNode* fast=head;
        ListNode* slow=head;
        if(head==NULL)return NULL;
        while(fast->next!=NULL&&fast->next->next!=NULL){
            fast=fast->next->next;
            slow=slow->next;
            xy++;
            if(slow==fast){//兩個指標相遇了
                slow=head;//一個退回原點，另一個從相遇節點繼續回圈
                while(slow!=fast){
                    fast=fast->next;
                    slow=slow->next;
                }
                return slow;//再相遇就是回圈入口節點
            }
        }
        return NULL;
    }
};

識訓摘要：雙指標yyds（這句話我已經說了千百遍~）
?????理解?x：頭節點-回圈入口節點
????????y：回圈入口節點-相遇節點
????????z：相遇節點-回圈入口節點
?????雙指標走過的路程以及這三個數之間的關系
?????還有一點需要注意的是：
????????當頭節點為NULL時，它肯定不能回圈，甚至不是個鏈表，直接回傳NULL即可，

學習的文章鏈接：https://programmercarl.com/0142.環形鏈表II.html#思路

學習的視頻鏈接：https://www.bilibili.com/video/BV1if4y1d7ob/?spm_id_from=333.788&vd_source=c2b246a405f861a2b3c13ab2b1b1eea6

學習時長：5h

標籤：其他

上一篇：2022.10.30每日一題

下一篇：2022年zzuli周賽(2)