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

題目鏈接：24. 兩兩交換鏈表中的節(jié)點(diǎn) - 力扣（LeetCode）

思路：

先定義一個(gè)虛擬頭結(jié)點(diǎn)方便操作。

再就是交換相鄰兩個(gè)元素了，此時(shí)一定要畫圖，不畫圖，操作多個(gè)指針很容易亂，而且要操作的先后順序

初始時(shí)，cur指向虛擬頭結(jié)點(diǎn)，然后進(jìn)行如下三步（比較懶直接用Carl哥圖了HH）：

?直觀一點(diǎ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* swapPairs(ListNode* head) {
        ListNode* dummyhead = new ListNode(0);
        dummyhead->next = head;
        ListNode* cur = dummyhead;
        //兩個(gè)都不為空時(shí)執(zhí)行交換
        while(cur->next != NULL && cur->next->next != NULL) {
            //兩個(gè)臨時(shí)節(jié)點(diǎn)存儲第二個(gè)交換數(shù)字的前后兩個(gè)數(shù)字
            ListNode* temp = cur->next;
            ListNode* tmp = cur->next->next->next;
            cur->next = cur->next->next;//第一步讓頭結(jié)點(diǎn)的下一個(gè)指針指向第二個(gè)交換數(shù)字
            cur->next->next = temp;//第二步讓第二個(gè)交換數(shù)字的指針指向第一個(gè)交換數(shù)字（已經(jīng)臨時(shí)存儲了，不然第一個(gè)數(shù)字丟失了）
            cur->next->next->next = tmp;//第三步讓此時(shí)的第一個(gè)交換數(shù)字（現(xiàn)在在第二個(gè)）的指針指向第三個(gè)數(shù)字
            cur = cur->next->next;//將執(zhí)行結(jié)點(diǎn)移動兩位進(jìn)行下一輪交換
        }
        return dummyhead->next;
    }
};

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

題目鏈接：??????19. 刪除鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn) - 力扣（LeetCode）

思路：

本人的思路是設(shè)置一個(gè)虛擬頭結(jié)點(diǎn)在頭結(jié)點(diǎn)前面遍歷一遍得出鏈表長度再減去輸入的數(shù)字，再遍歷一遍后直接將倒數(shù)第n+1個(gè)結(jié)點(diǎn)接在第n-1個(gè)結(jié)點(diǎn)后面，是可行的。（跟Carl哥雙指針差不多思路）

/**
 * 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);
        int x = 0;
        dummyhead->next = head;
        ListNode* cur = dummyhead;
        //設(shè)置一個(gè)虛擬頭結(jié)點(diǎn)在頭結(jié)點(diǎn)前面遍歷一遍得出鏈表長度再減去輸入的數(shù)字
        while(cur->next != NULL) {
            cur = cur->next;
            x++;
        }
        ListNode* cur1 = dummyhead;
        int m = x - n;
        //再遍歷一遍后直接將倒數(shù)第n+1個(gè)結(jié)點(diǎn)接在第n-1個(gè)結(jié)點(diǎn)后面
        while(m != 0) {
            cur1 = cur1->next;
            m--;
        }
        cur1->next = cur1->next->next;
        return dummyhead->next;
    }
};

Carl哥思路：

雙指針的經(jīng)典應(yīng)用，如果要?jiǎng)h除倒數(shù)第n個(gè)節(jié)點(diǎn)，讓fast移動n步，然后讓fast和slow同時(shí)移動，直到fast指向鏈表末尾。刪掉slow所指向的節(jié)點(diǎn)就可以了。

思路是這樣的，但要注意一些細(xì)節(jié)。

分為如下幾步：

• 首先這里我推薦大家使用虛擬頭結(jié)點(diǎn)，這樣方便處理刪除實(shí)際頭結(jié)點(diǎn)的邏輯。

• 定義fast指針和slow指針，初始值為虛擬頭結(jié)點(diǎn)。

• fast首先走n + 1步 ，為什么是n+1呢，因?yàn)橹挥羞@樣同時(shí)移動的時(shí)候slow才能指向刪除節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)（方便做刪除操作）。

• fast和slow同時(shí)移動，直到fast指向末尾。

• 刪除slow指向的下一個(gè)節(jié)點(diǎn)。

LeetCode160.鏈表相交

題目鏈接：面試題 02.07. 鏈表相交 - 力扣（LeetCode）

?思路：

該題目就是求兩個(gè)鏈表交點(diǎn)節(jié)點(diǎn)的指針。 但要注意：交點(diǎn)不是數(shù)值相等，而是指針相等。

先求出兩個(gè)鏈表的長度，并求出兩個(gè)鏈表長度的差值，然后讓curA移動到，和curB 末尾對齊的位置。

此時(shí)就可以比較curA和curB是否相同，如果不相同，同時(shí)向后移動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) {
        int a = 0,b = 0;
        ListNode* cur1 = headA;
        ListNode* cur2 = headB;
        //遍歷鏈表A和鏈表B,注意此時(shí)指針直接指向頭結(jié)點(diǎn)，無虛擬頭結(jié)點(diǎn)，也就是指向第一個(gè)結(jié)點(diǎn)，因此不能用cur->next,否則會在NULL時(shí)繼續(xù)指向下一個(gè)而報(bào)錯(cuò)
        while(cur1 != NULL) {
            cur1 = cur1->next;
            a++;
        }
        while(cur2 != NULL) {
            cur2 = cur2->next;
            b++;
        }
        //重置cur1,cur2的起始位置
        cur1 = headA;
        cur2 = headB;
        // 讓cur1為最長鏈表的頭，a為其長度
        if(b > a) {
            swap(a,b);
            swap(cur1,cur2);
        }
        //長度差
        int  x = a -b;
        //鏈表a,b對齊
        while(x--) {
            cur1 = cur1->next;
        }
        while(cur1 != NULL) {
            if(cur1 == cur2) {
                return cur1;
            }
            cur1 = cur1->next;
            cur2 = cur2->next;
        }
        return NULL;
    }
};

?LeetCode142.環(huán)形鏈表II

題目鏈接：142. 環(huán)形鏈表 II - 力扣（LeetCode）

思路：

1.判斷鏈表是否有環(huán)

可以使用快慢指針法，分別定義 fast 和 slow 指針，從頭結(jié)點(diǎn)出發(fā)，fast指針每次移動兩個(gè)節(jié)點(diǎn)，slow指針每次移動一個(gè)節(jié)點(diǎn)，如果 fast 和 slow指針在途中相遇 ，說明這個(gè)鏈表有環(huán)。

為什么fast 走兩個(gè)節(jié)點(diǎn)，slow走一個(gè)節(jié)點(diǎn)，有環(huán)的話，一定會在環(huán)內(nèi)相遇呢，而不是永遠(yuǎn)的錯(cuò)開呢。

首先第一點(diǎn)：fast指針一定先進(jìn)入環(huán)中，如果fast指針和slow指針相遇的話，一定是在環(huán)中相遇，這是毋庸置疑的。

fast指針和slow指針一定會相遇。

fast和slow各自再走一步， fast和slow就相遇了。

這是因?yàn)閒ast是走兩步，slow是走一步，其實(shí)相對于slow來說，fast是一個(gè)節(jié)點(diǎn)一個(gè)節(jié)點(diǎn)的靠近slow的，所以fast一定可以和slow重合。

2.如果有環(huán)，如何找到這個(gè)環(huán)的入口

此時(shí)已經(jīng)可以判斷鏈表是否有環(huán)了，那么接下來要找這個(gè)環(huán)的入口了。

假設(shè)從頭結(jié)點(diǎn)到環(huán)形入口節(jié)點(diǎn) 的節(jié)點(diǎn)數(shù)為x。 環(huán)形入口節(jié)點(diǎn)到 fast指針與slow指針相遇節(jié)點(diǎn) 節(jié)點(diǎn)數(shù)為y。 從相遇節(jié)點(diǎn) 再到環(huán)形入口節(jié)點(diǎn)節(jié)點(diǎn)數(shù)為 z。 如圖所示：

那么相遇時(shí)： slow指針走過的節(jié)點(diǎn)數(shù)為:?x + y， fast指針走過的節(jié)點(diǎn)數(shù)：x + y + n (y + z)，n為fast指針在環(huán)內(nèi)走了n圈才遇到slow指針， （y+z）為 一圈內(nèi)節(jié)點(diǎn)的個(gè)數(shù)A。

因?yàn)閒ast指針是一步走兩個(gè)節(jié)點(diǎn)，slow指針一步走一個(gè)節(jié)點(diǎn)， 所以 fast指針走過的節(jié)點(diǎn)數(shù) = slow指針走過的節(jié)點(diǎn)數(shù) * 2：

(x + y) * 2 = x + y + n (y + z)

兩邊消掉一個(gè)（x+y）:?x + y = n (y + z)

因?yàn)橐噎h(huán)形的入口，那么要求的是x，因?yàn)閤表示 頭結(jié)點(diǎn)到 環(huán)形入口節(jié)點(diǎn)的的距離。

所以要求x ，將x單獨(dú)放在左面：x = n (y + z) - y?,

再從n(y+z)中提出一個(gè) （y+z）來，整理公式之后為如下公式：x = (n - 1) (y + z) + z?注意這里n一定是大于等于1的，因?yàn)?fast指針至少要多走一圈才能相遇slow指針。

這個(gè)公式說明什么呢？

先拿n為1的情況來舉例，意味著fast指針在環(huán)形里轉(zhuǎn)了一圈之后，就遇到了 slow指針了。

當(dāng) n為1的時(shí)候，公式就化解為?x = z，

這就意味著，從頭結(jié)點(diǎn)出發(fā)一個(gè)指針，從相遇節(jié)點(diǎn) 也出發(fā)一個(gè)指針，這兩個(gè)指針每次只走一個(gè)節(jié)點(diǎn)， 那么當(dāng)這兩個(gè)指針相遇的時(shí)候就是 環(huán)形入口的節(jié)點(diǎn)。

也就是在相遇節(jié)點(diǎn)處，定義一個(gè)指針index1，在頭結(jié)點(diǎn)處定一個(gè)指針index2。

讓index1和index2同時(shí)移動，每次移動一個(gè)節(jié)點(diǎn)， 那么他們相遇的地方就是 環(huán)形入口的節(jié)點(diǎn)。

當(dāng)n>1時(shí)，與極端情況一樣，不過index1是走了n-1圈后與index2相遇。文章來源地址http://www.zghlxwxcb.cn/news/detail-488087.html

/**
 * 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) {
            slow = slow->next;
            fast = fast->next->next;
            //快慢指針相遇，此時(shí)從head和相遇點(diǎn)開始查找，直到相遇
            if(slow == fast) {
                ListNode* index1 = fast;
                ListNode* index2 = head;
                while(index1 != index2) {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index2;//返回環(huán)的入口
            }
        }
        return NULL;
    }
};

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