本文章代碼以c++為例！

一、力扣第24題：兩兩交換鏈表中的節(jié)點(diǎn)

?

給定一個(gè)鏈表，兩兩交換其中相鄰的節(jié)點(diǎn)，并返回交換后的鏈表。

你不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值，而是需要實(shí)際的進(jìn)行節(jié)點(diǎn)交換。

思路：

這道題建議使用虛擬頭結(jié)點(diǎn)，這樣會(huì)方便很多，要不然每次針對(duì)頭結(jié)點(diǎn)（沒有前一個(gè)指針指向頭結(jié)點(diǎn)），還要單獨(dú)處理。

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

初始時(shí)，cur指向虛擬頭結(jié)點(diǎn)，然后進(jìn)行如下三步，操作之后，鏈表如下：：

看這個(gè)可能就更直觀一些了：

對(duì)應(yīng)的C++代碼實(shí)現(xiàn)如下： （注釋中詳細(xì)和如上圖中的三步做對(duì)應(yīng)）：

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)

二、力扣第19題：刪除鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn)

?思路：

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

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

分為如下幾步：

此時(shí)不難寫出如下C++代碼：

二、力扣：面試題 02.07. 鏈表相交

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

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

• 

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

• fast和slow同時(shí)移動(dòng)，直到fast指向末尾，如題：

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

  C++代碼：

  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;
      }
  };
  

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

示例 1：

示例 2：

示例 3：

思路

簡(jiǎn)單來說，就是求兩個(gè)鏈表交點(diǎn)節(jié)點(diǎn)的指針。 這里同學(xué)們要注意，交點(diǎn)不是數(shù)值相等，而是指針相等。

為了方便舉例，假設(shè)節(jié)點(diǎn)元素?cái)?shù)值相等，則節(jié)點(diǎn)指針相等。

看如下兩個(gè)鏈表，目前curA指向鏈表A的頭結(jié)點(diǎn)，curB指向鏈表B的頭結(jié)點(diǎn)：

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

此時(shí)我們就可以比較curA和curB是否相同，如果不相同，同時(shí)向后移動(dòng)curA和curB，如果遇到curA == curB，則找到交點(diǎn)。

否則循環(huán)退出返回空指針。

C++代碼如下：

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* curA = headA;
        ListNode* curB = headB;
        int lenA = 0, lenB = 0;
        while (curA != NULL) { // 求鏈表A的長(zhǎng)度
            lenA++;
            curA = curA->next;
        }
        while (curB != NULL) { // 求鏈表B的長(zhǎng)度
            lenB++;
            curB = curB->next;
        }
        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;
        // 讓curA和curB在同一起點(diǎn)上（末尾位置對(duì)齊）
        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)

一、力扣第142題：環(huán)形鏈表 II

思路

這道題目，不僅考察對(duì)鏈表的操作，而且還需要一些數(shù)學(xué)運(yùn)算。

主要考察兩知識(shí)點(diǎn)：

• 判斷鏈表是否環(huán)
• 如果有環(huán)，如何找到這個(gè)環(huán)的入口

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

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

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

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

那么來看一下，為什么fast指針和slow指針一定會(huì)相遇呢？

可以畫一個(gè)環(huán)，然后讓 fast指針在任意一個(gè)節(jié)點(diǎn)開始追趕slow指針。

會(huì)發(fā)現(xiàn)最終都是這種情況， 如下圖：

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

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

動(dòng)畫如下：

# 如果有環(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í)移動(dòng)，每次移動(dòng)一個(gè)節(jié)點(diǎn)， 那么他們相遇的地方就是 環(huán)形入口的節(jié)點(diǎn)。

動(dòng)畫如下：

那么 n如果大于1是什么情況呢，就是fast指針在環(huán)形轉(zhuǎn)n圈之后才遇到 slow指針。

其實(shí)這種情況和n為1的時(shí)候 效果是一樣的，一樣可以通過這個(gè)方法找到 環(huán)形的入口節(jié)點(diǎn)，只不過，index1 指針在環(huán)里 多轉(zhuǎn)了(n-1)圈，然后再遇到index2，相遇點(diǎn)依然是環(huán)形的入口節(jié)點(diǎn)。

代碼如下：

/**
 * 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)，同時(shí)查找直至相遇
            if (slow == fast) {
                ListNode* index1 = fast;
                ListNode* index2 = head;
                while (index1 != index2) {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index2; // 返回環(huán)的入口
            }
        }
        return NULL;
    }
};

• 時(shí)間復(fù)雜度: O(n)，快慢指針相遇前，指針走的次數(shù)小于鏈表長(zhǎng)度，快慢指針相遇后，兩個(gè)index指針走的次數(shù)也小于鏈表長(zhǎng)度，總體為走的次數(shù)小于 2n
• 空間復(fù)雜度: O(1)

補(bǔ)充

在推理過程中，大家可能有一個(gè)疑問就是：為什么第一次在環(huán)中相遇，slow的 步數(shù) 是 x+y 而不是 x + 若干環(huán)的長(zhǎng)度 + y 呢？

即文章鏈表：環(huán)找到了，那入口呢？

(opens new window)中如下的地方：

首先slow進(jìn)環(huán)的時(shí)候，fast一定是先進(jìn)環(huán)來了。

如果slow進(jìn)環(huán)入口，fast也在環(huán)入口，那么把這個(gè)環(huán)展開成直線，就是如下圖的樣子：

可以看出如果slow 和 fast同時(shí)在環(huán)入口開始走，一定會(huì)在環(huán)入口3相遇，slow走了一圈，fast走了兩圈。

重點(diǎn)來了，slow進(jìn)環(huán)的時(shí)候，fast一定是在環(huán)的任意一個(gè)位置，如圖：

那么fast指針走到環(huán)入口3的時(shí)候，已經(jīng)走了k + n 個(gè)節(jié)點(diǎn)，slow相應(yīng)的應(yīng)該走了(k + n) / 2 個(gè)節(jié)點(diǎn)。

因?yàn)閗是小于n的（圖中可以看出），所以(k + n) / 2 一定小于n。

也就是說slow一定沒有走到環(huán)入口3，而fast已經(jīng)到環(huán)入口3了。

這說明什么呢？

在slow開始走的那一環(huán)已經(jīng)和fast相遇了。

那有同學(xué)又說了，為什么fast不能跳過去呢？ 在剛剛已經(jīng)說過一次了，fast相對(duì)于slow是一次移動(dòng)一個(gè)節(jié)點(diǎn)，所以不可能跳過去。

好了，這次把為什么第一次在環(huán)中相遇，slow的 步數(shù) 是 x+y 而不是 x + 若干環(huán)的長(zhǎng)度 + y ，用數(shù)學(xué)推理了一下，算是對(duì)鏈表：環(huán)找到了，那入口呢？

(opens new window)的補(bǔ)充。

day4（補(bǔ)打卡）文章來源地址http://www.zghlxwxcb.cn/news/detail-618261.html

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