0.引言

● 24. 兩兩交換鏈表中的節(jié)點
● 19.刪除鏈表的倒數(shù)第N個節(jié)點
● 160.鏈表相交
● 142.環(huán)形鏈表II

1. 兩兩交換鏈表中的節(jié)點

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

示例 1：

image.png

輸入：head = [1,2,3,4]
輸出：[2,1,4,3]

示例 2：

輸入：head = []
輸出：[]

示例 3：

輸入：head = [1]
輸出：[1]

提示：

• 鏈表中節(jié)點的數(shù)目在范圍 [0, 100] 內(nèi)
• 0 <= Node.val <= 100

Discussion | Solution

1.1.自己想法及代碼實現(xiàn)

假設(shè)有三個節(jié)點，首先備份第三個節(jié)點，然后對起那兩個節(jié)點進行交換。

需要畫圖梳理，特別是 break那里：

24-2.jpg

/*
 * @lc app=leetcode.cn id=24 lang=cpp
 *
 * [24] 兩兩交換鏈表中的節(jié)點
 */

// @lc code=start
/**
 * 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) {
    if (head == nullptr || head->next == nullptr) return head;
    ListNode* fake_head = new ListNode(0);
    fake_head->next = head;
    ListNode* pre = fake_head;
    ListNode* cur = pre->next;
    ListNode* nxt = cur->next;
    while (nxt) {
      ListNode* nnxt = nxt->next;
      pre->next = nxt;
      nxt->next = cur;
      cur->next = nnxt;
      pre = pre->next->next;  // 往前走兩步
      cur = pre->next;
      if (cur == nullptr) break;
      nxt = cur->next;
    }
    head = fake_head->next;
    delete fake_head;
    return head;
  }
};

1.2.參考思路及代碼實現(xiàn)

先占坑。

2. 刪除鏈表的倒數(shù)第 N 個結(jié)點

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

示例 1：

image.png

輸入：head = [1,2,3,4,5], n = 2
輸出：[1,2,3,5]

示例 2：

輸入：head = [1], n = 1
輸出：[]

示例 3：

輸入：head = [1,2], n = 1
輸出：[1]

提示：

• 鏈表中結(jié)點的數(shù)目為 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

進階：你能嘗試使用一趟掃描實現(xiàn)嗎？

Discussion | Solution

2.1.自己想法及代碼實現(xiàn)

• 很久以前好像做過這個題：快慢指針法，快慢指針間距固定為k，快的到尾巴了，慢的就在倒數(shù)第k個節(jié)點上。

  
  
  19-2.jpg

/*
 * @lc app=leetcode.cn id=19 lang=cpp
 *
 * [19] 刪除鏈表的倒數(shù)第 N 個結(jié)點
 */

// @lc code=start
/**
 * 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) {
    if (head == nullptr || n == 0) return head;
    // 還是要fake_head,因為刪除的節(jié)點有可能是頭結(jié)點
    ListNode* fake_head = new ListNode(0);
    fake_head->next = head;
    ListNode* fast = fake_head;
    ListNode* slow = fake_head;
    while (n--) {
      fast = fast->next;
    }
    while (fast->next) {
      fast = fast->next;
      slow = slow->next;
    }
    slow->next = slow->next->next;
    head = fake_head->next;
    delete fake_head;
    return head;
  }
};
// @lc code=end

2.2.參考想法及代碼實現(xiàn)

先占坑.

3.相交鏈表

給你兩個單鏈表的頭節(jié)點 headA 和 headB ，請你找出并返回兩個單鏈表相交的起始節(jié)點。如果兩個鏈表不存在相交節(jié)點，返回 null 。

圖示兩個鏈表在節(jié)點 c1 開始相交：

image.png

題目數(shù)據(jù) 保證 整個鏈式結(jié)構(gòu)中不存在環(huán)。

注意，函數(shù)返回結(jié)果后，鏈表必須 保持其原始結(jié)構(gòu) 。

自定義評測：

評測系統(tǒng) 的輸入如下（你設(shè)計的程序 不適用 此輸入）：

• intersectVal - 相交的起始節(jié)點的值。如果不存在相交節(jié)點，這一值為 0
• listA - 第一個鏈表
• listB - 第二個鏈表
• skipA - 在 listA 中（從頭節(jié)點開始）跳到交叉節(jié)點的節(jié)點數(shù)
• skipB - 在 listB 中（從頭節(jié)點開始）跳到交叉節(jié)點的節(jié)點數(shù)

評測系統(tǒng)將根據(jù)這些輸入創(chuàng)建鏈式數(shù)據(jù)結(jié)構(gòu)，并將兩個頭節(jié)點 headA 和 headB 傳遞給你的程序。如果程序能夠正確返回相交節(jié)點，那么你的解決方案將被 視作正確答案 。

示例 1：

image.png

輸入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
輸出：Intersected at '8'
解釋：相交節(jié)點的值為 8 （注意，如果兩個鏈表相交則不能為 0）。
從各自的表頭開始算起，鏈表 A 為 [4,1,8,4,5]，鏈表 B 為 [5,6,1,8,4,5]。
在 A 中，相交節(jié)點前有 2 個節(jié)點；在 B 中，相交節(jié)點前有 3 個節(jié)點。
— 請注意相交節(jié)點的值不為 1，因為在鏈表 A 和鏈表 B 之中值為 1 的節(jié)點 (A 中第二個節(jié)點和 B 中第三個節(jié)點) 是不同的節(jié)點。換句話說，它們在內(nèi)存中指向兩個不同的位置，而鏈表 A 和鏈表 B 中值為 8 的節(jié)點 (A 中第三個節(jié)點，B 中第四個節(jié)點) 在內(nèi)存中指向相同的位置。

示例 2：

image.png

輸入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
輸出：Intersected at '2'
解釋：相交節(jié)點的值為 2 （注意，如果兩個鏈表相交則不能為 0）。
從各自的表頭開始算起，鏈表 A 為 [1,9,1,2,4]，鏈表 B 為 [3,2,4]。
在 A 中，相交節(jié)點前有 3 個節(jié)點；在 B 中，相交節(jié)點前有 1 個節(jié)點。

示例 3：

image.png

輸入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
輸出：null
解釋：從各自的表頭開始算起，鏈表 A 為 [2,6,4]，鏈表 B 為 [1,5]。
由于這兩個鏈表不相交，所以 intersectVal 必須為 0，而 skipA 和 skipB 可以是任意值。
這兩個鏈表不相交，因此返回 null 。

提示：

• listA 中節(jié)點數(shù)目為 m
• listB 中節(jié)點數(shù)目為 n
• 1 <= m, n <= 3 * 10<sup>4</sup>
• 1 <= Node.val <= 10<sup>5</sup>
• 0 <= skipA <= m
• 0 <= skipB <= n
• 如果 listA 和 listB 沒有交點，intersectVal 為 0
• 如果 listA 和 listB 有交點，intersectVal == listA[skipA] == listB[skipB]

進階：你能否設(shè)計一個時間復雜度 O(m + n) 、僅用 O(1) 內(nèi)存的解決方案？

Discussion | Solution

3.1.自己想法及代碼實現(xiàn)

• 暴力求解，兩個for循環(huán)，就不寫了
• 利用set

/*
 * @lc app=leetcode.cn id=160 lang=cpp
 *
 * [160] 相交鏈表
 */

// @lc code=start
/**
 * 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) {
        if(headA == nullptr|| headB == nullptr){
            return nullptr;
        }
        std::set<ListNode*> check_set;
        ListNode* tmp = headA;
        while(tmp){
            check_set.insert(tmp);
            tmp = tmp->next;
        }
        tmp = headB;
        while(tmp){
            if(check_set.find(tmp) != check_set.end())
            return tmp;
            tmp = tmp->next;
        }
        return nullptr;
    }
};

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

給定一個鏈表的頭節(jié)點 head ，返回鏈表開始入環(huán)的第一個節(jié)點。 如果鏈表無環(huán)，則返回 null。

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

**不允許修改 **鏈表。

示例 1：

image.png

輸入：head = [3,2,0,-4], pos = 1
輸出：返回索引為 1 的鏈表節(jié)點
解釋：鏈表中有一個環(huán)，其尾部連接到第二個節(jié)點。

示例 2：

image.png

輸入：head = [1,2], pos = 0
輸出：返回索引為 0 的鏈表節(jié)點
解釋：鏈表中有一個環(huán)，其尾部連接到第一個節(jié)點。

示例 3：

image.png

輸入：head = [1], pos = -1
輸出：返回 null
解釋：鏈表中沒有環(huán)。

提示：

• 鏈表中節(jié)點的數(shù)目范圍在范圍 [0, 10<sup>4</sup>] 內(nèi)
• -10<sup>5</sup> <= Node.val <= 10<sup>5</sup>
• pos 的值為 -1 或者鏈表中的一個有效索引

進階：你是否可以使用 O(1) 空間解決此題？

Discussion | Solution

4.1.自己想法及代碼實現(xiàn)

• 同樣利用set

/**
 * 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) {
        std::set<ListNode*> check_node;
        while(head){
            check_node.insert(head);
            head = head->next;
            if(check_node.find(head) != check_node.end()){
                return head;
            }
        }
        return nullptr;
    }
};

這個題目以前也做過，快慢指針法利用如下原理：

142-4.jpg

/*
 * @lc app=leetcode.cn id=142 lang=cpp
 *
 * [142] 環(huán)形鏈表 II
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * 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) {
    if (head == nullptr || head->next == nullptr) return nullptr;
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast->next && slow) {
      if (fast->next->next == nullptr) return nullptr;
      slow = slow->next;
      fast = fast->next->next;
      if (slow == fast) {
        break;
      }
    }
    while (slow) {
      if (slow == head) {
        return slow;
      }
      slow = slow->next;
      head = head->next;
    }
    // std::cout << tmp->val << " ";
    return nullptr;
  }
};

// @lc code=end

5.總結(jié)

• 鏈表里面的快慢指針也是很常見的用法；
• 鏈表的題畫一下圖，思路更清晰。