day4 | 24. 兩兩交換鏈表中的節(jié)點(diǎn)、19.刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)、面試題 02.07. 鏈表相交、 142.環(huán)形鏈表II

這篇具有很好參考價(jià)值的文章主要介紹了day4 | 24. 兩兩交換鏈表中的節(jié)點(diǎn)、19.刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)、面試題 02.07. 鏈表相交、 142.環(huán)形鏈表II。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問(wèn)。

鏈接

題目鏈接：

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

https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

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

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

解題及思路學(xué)習(xí)

24. 兩兩交換鏈表中的節(jié)點(diǎn)

給你一個(gè)鏈表，兩兩交換其中相鄰的節(jié)點(diǎn)，并返回交換后鏈表的頭節(jié)點(diǎn)。你必須在不修改節(jié)點(diǎn)內(nèi)部的值的情況下完成本題（即，只能進(jìn)行節(jié)點(diǎn)交換）。

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-WW55AwAZ-1685353234158)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/f8f59f5e-54f6-4786-8fbf-16f18602a402/Untitled.png)]

自己想法：可以拆分為交換兩個(gè)相鄰節(jié)點(diǎn)。只有一個(gè)或者沒(méi)有節(jié)點(diǎn)時(shí)，不交換?？梢杂脙蓚€(gè)指針來(lái)分別表示前后兩個(gè)節(jié)點(diǎn)。應(yīng)該還需要一個(gè)節(jié)點(diǎn)來(lái)暫存后面的值。

自己想法的代碼實(shí)現(xiàn)：

（有點(diǎn)繞，下次遇見(jiàn)這種，可以拿張草稿紙畫(huà)一下）

/**
 * 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* pre;
        ListNode* cur;
        ListNode* dummyHead = new ListNode(0);
        dummyHead -> next = head;
        pre = dummyHead;
        cur = head;
        ListNode* tmp;
        
        while(cur != NULL && cur -> next != NULL){
            pre ->next =cur -> next;
            tmp = cur -> next -> next;
            pre -> next -> next = cur;
            cur -> next = tmp;

            pre = cur;
            cur = cur -> next;
        }

        tmp = dummyHead -> next;
        delete dummyHead;
        return tmp;

    }
};

隨想錄想法：步驟差不多，不過(guò)是用一個(gè)指針cur和兩個(gè)臨時(shí)指針來(lái)分別表示cur前面一個(gè)和后面一個(gè)節(jié)點(diǎn)。

代碼實(shí)現(xiàn)：

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyHead = new ListNode(0); // 設(shè)置一個(gè)虛擬頭結(jié)點(diǎn)
        dummyHead->next = head; // 將虛擬頭結(jié)點(diǎn)指向head，這樣方面后面做刪除操作
        ListNode* cur = dummyHead;
        while(cur->next != nullptr && cur->next->next != nullptr) {
            ListNode* tmp = cur->next; // 記錄臨時(shí)節(jié)點(diǎn)
            ListNode* tmp1 = cur->next->next->next; // 記錄臨時(shí)節(jié)點(diǎn)

            cur->next = cur->next->next;    // 步驟一
            cur->next->next = tmp;          // 步驟二
            cur->next->next->next = tmp1;   // 步驟三

            cur = cur->next->next; // cur移動(dòng)兩位，準(zhǔn)備下一輪交換
        }
        return dummyHead->next;
    }
};

時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(1)

其實(shí)兩種方法的思路都差不多，不過(guò)代碼隨想錄的方法更加簡(jiǎn)潔，不容易繞暈。一定要畫(huà)圖，不畫(huà)圖，操作多個(gè)指針很容易亂，而且要操作的先后順序。

19.?刪除鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn)

給你一個(gè)鏈表，刪除鏈表的倒數(shù)第?n?**個(gè)結(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-lmqBLS3e-1685353234162)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/ac022418-b4c3-488b-8f50-97ed27d7879a/Untitled.png)]

自己思路：刪除倒數(shù)第n個(gè)，對(duì)于單鏈表來(lái)說(shuō)，得先知道長(zhǎng)度吧。先確定范圍，n是要小于整個(gè)鏈表長(zhǎng)度的。可以用雙指針（當(dāng)右指針移動(dòng)了n個(gè)節(jié)點(diǎn)時(shí)，才生成左節(jié)點(diǎn)），左指針落后右指針n個(gè)長(zhǎng)度。當(dāng)后面一個(gè)指針的next為NULL時(shí)，表示到底了，這個(gè)時(shí)候刪除前面一個(gè)指針的下一個(gè)節(jié)點(diǎn)。刪除節(jié)點(diǎn)需要一個(gè)臨時(shí)節(jié)點(diǎn)，用來(lái)記錄刪除節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)(方便內(nèi)存釋放，如果不需要釋放內(nèi)存，則不需要臨時(shí)節(jié)點(diǎn)）。

代碼實(shí)現(xiàn):

/**
 * 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) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead -> next = head;
        ListNode* right = dummyHead;
        ListNode* left = dummyHead; 
        int count = 0;

        while(count < n && right != NULL){
            right = right -> next;
            count++;
        }
        right = right -> next;
        while(count >= n && right  != NULL){
            right = right -> next;
            left = left -> next;
            count++;
        }
       
       // left->next = left->next->next;   不釋放內(nèi)存的寫(xiě)法

        ListNode* tmp = left -> next;
        left->next = tmp->next;
        delete tmp;

        return dummyHead-> next;
    }
};

代碼隨想錄思路：運(yùn)用雙指針，快慢指針。我的思路跟這個(gè)一樣。不同之處在于我用了一個(gè)計(jì)數(shù)的變量，但是隨想錄直接用n計(jì)數(shù)，更加簡(jiǎn)潔。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* slow = dummyHead;
        ListNode* fast = dummyHead;
        while(n-- && fast != NULL) {
            fast = fast->next;
        }
        fast = fast->next; // fast再提前走一步，因?yàn)樾枰宻low指向刪除節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)
        while (fast != NULL) {
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next; 
        
        // ListNode *tmp = slow->next;  C++釋放內(nèi)存的邏輯
        // slow->next = tmp->next;
        // delete nth;
        
        return dummyHead->next;
    }
};

我剛開(kāi)始是沒(méi)有調(diào)通的，因?yàn)槲矣脕?lái)head作為快慢指針的頭節(jié)點(diǎn)。但是這樣，當(dāng)要?jiǎng)h除的就是頭節(jié)點(diǎn)的時(shí)候就很不好操作。使用虛擬頭節(jié)點(diǎn)的方式，更加高效。

面試題 02.07.?鏈表相交

給你兩個(gè)單鏈表的頭節(jié)點(diǎn)?headA?和?headB?，請(qǐng)你找出并返回兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。如果兩個(gè)鏈表沒(méi)有交點(diǎn)，返回?null?。

圖示兩個(gè)鏈表在節(jié)點(diǎn)?c1?開(kāi)始相交**：**

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-IIs2Tp7E-1685353234163)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/777bc3bd-2996-4638-992b-10a85191e10f/Untitled.png)]

自己思路：給定兩個(gè)單鏈表頭節(jié)點(diǎn)，那我可以分別遍歷兩個(gè)鏈表。值相等不等于相交，交叉點(diǎn)的地址是相同的。鏈表不一定等長(zhǎng)和相交。如果兩個(gè)鏈表中，當(dāng)前兩個(gè)節(jié)點(diǎn)地址不等，但是這兩個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)地址相等，則下一個(gè)節(jié)點(diǎn)就是相交點(diǎn)。暴力一點(diǎn)的解法：先遍歷一個(gè)鏈表的所有節(jié)點(diǎn)并記錄其地址。之后用另一個(gè)鏈表的每個(gè)節(jié)點(diǎn)去比對(duì)。

隨想錄思路：簡(jiǎn)單來(lái)說(shuō)，就是求兩個(gè)鏈表交點(diǎn)節(jié)點(diǎn)的指針。要注意，交點(diǎn)不是數(shù)值相等，而是指針相等。

求出兩個(gè)鏈表的長(zhǎng)度，并求出兩個(gè)鏈表長(zhǎng)度的差值，然后讓curA移動(dòng)到，和curB 末尾對(duì)齊的位置，如圖：

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-4QXryNvN-1685353234163)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/8c1662a5-2c35-4575-9dbd-d6c635bf90d6/Untitled.png)]

此時(shí)我們就可以比較curA和curB是否相同，如果不相同，同時(shí)向后移動(dòng)curA和curB，如果遇到curA == curB，則找到交點(diǎn)。否則循環(huán)退出返回空指針。

/**
 * 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 = headA;
        ListNode* curB = headB;
        int lenA = 0, lenB = 0;
        //求鏈表長(zhǎng)度
        while(curA !=NULL){
            curA = curA-> next;
            lenA++;
        }
        while(curB != NULL){
            curB = curB -> next;
            lenB++;
        }
        curA = headA;
        curB = headB;

        // 讓curA為最長(zhǎng)鏈表的頭，lenA為其長(zhǎng)度
        if(lenB > lenA){
            swap(lenA, lenB);
            swap(curA, curB);
        }
        //求長(zhǎng)度差
        int gap = lenA -lenB;
        while(gap--){
            curA = curA->next;
        }
        //遍歷curA和curB，遇到相同值則直接返回
        while(curA != NULL){
            if(curA == curB){
                return curA;
            }
            curA = curA->next;
            curB = curB->next;
        }
        return NULL;
    }
};

時(shí)間復(fù)雜度：O(n + m)
空間復(fù)雜度：O(1

這道題，我沒(méi)有想到先去對(duì)齊，這樣來(lái)簡(jiǎn)化一下。以后遇見(jiàn)這種長(zhǎng)度不一，然后又要匹配中間某一個(gè)的題，都可以考慮先將長(zhǎng)度對(duì)其，再來(lái)尋找中間值。

142.環(huán)形鏈表II

給定一個(gè)鏈表的頭節(jié)點(diǎn) ?head?，返回鏈表開(kāi)始入環(huán)的第一個(gè)節(jié)點(diǎn)。?如果鏈表無(wú)環(huán)，則返回?null。

如果鏈表中有某個(gè)節(jié)點(diǎn)，可以通過(guò)連續(xù)跟蹤?next?指針再次到達(dá)，則鏈表中存在環(huán)。為了表示給定鏈表中的環(huán)，評(píng)測(cè)系統(tǒng)內(nèi)部使用整數(shù)?pos?來(lái)表示鏈表尾連接到鏈表中的位置（索引從 0 開(kāi)始）。如果?pos?是?-1，則在該鏈表中沒(méi)有環(huán)。注意：pos?不作為參數(shù)進(jìn)行傳遞，僅僅是為了標(biāo)識(shí)鏈表的實(shí)際情況。不允許修改?鏈表。

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-991IVTfC-1685353234164)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/efbecd61-9d24-4ce9-a8ca-501bc2be8ec5/Untitled.png)]

自己思考：沒(méi)啥好的思路。只想到暴力的，先記錄所有已遍歷點(diǎn)，遍歷下一個(gè)點(diǎn)的時(shí)候就進(jìn)行比對(duì)。

隨想錄思路：（牛逼），利用快慢指針來(lái)判斷是否有環(huán)，以及確定有環(huán)后點(diǎn)的選取。具體思路：https://programmercarl.com/0142.環(huán)形鏈表II.html#思路

其中涉及到很多數(shù)學(xué)推理。主要思想是利用速度差來(lái)解決。

/**
 * 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) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast != NULL && fast->next != NULL){
            //兩個(gè)指針移動(dòng)的速度快慢不一樣，一個(gè)1，一個(gè)2
            slow = slow -> next;
            fast = fast->next->next;
            // 快慢指針相遇，此時(shí)從head 和 相遇點(diǎn)，同時(shí)查找直至相遇
            //根據(jù)數(shù)學(xué)推理，從head和快慢指針相遇點(diǎn)到交點(diǎn)距離相等
            if(slow == fast){
                ListNode* index1 = fast;
                ListNode* index2 = head;
                while(index1 != index2){
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index2;
            }
        }
        return NULL;
    }
};

困難及收獲

困難

1、有時(shí)候有思路，但是在代碼細(xì)節(jié)上容易出現(xiàn)錯(cuò)誤。以后多注意邊界情況，可以的話畫(huà)圖來(lái)進(jìn)行輔助

2、數(shù)學(xué)原理容易理解，但是沒(méi)見(jiàn)過(guò)這道題的話，一時(shí)半會(huì)兒很難想到。多積累吧。

今日收獲

鏈表總結(jié)：https://programmercarl.com/鏈表總結(jié)篇.html#鏈表的理論基礎(chǔ)

鏈表的長(zhǎng)度問(wèn)題，最好找到其共同路段。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-499963.html

到了這里，關(guān)于day4 | 24. 兩兩交換鏈表中的節(jié)點(diǎn)、19.刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)、面試題 02.07. 鏈表相交、 142.環(huán)形鏈表II的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！