LeetCode_LinkedList_142. Linked List Cycle II 環形連結清單 II（C++/Java）【快慢指針】

目錄

​​一，題目描述​​

​​英文描述​​

​​中文描述​​

​​二，解題思路​​

​​三，AC代碼​​

​​C++​​

​​Java​​

​​四，解題過程​​

​​第一博​​

一，題目描述

英文描述

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Notice that you should not modify the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1 Output: tail connects to node index 1 Explanation: There is a cycle in the linked list, where tail connects to the second node.

中文描述

給定一個連結清單，傳回連結清單開始入環的第一個節點。 如果連結清單無環，則傳回 null。

為了表示給定連結清單中的環，我們使用整數 pos 來表示連結清單尾連接配接到連結清單中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該連結清單中沒有環。注意，pos 僅僅是用于辨別環的情況，并不會作為參數傳遞到函數中。

說明：不允許修改給定的連結清單。

進階：

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

示例 1：

輸入：head = [3,2,0,-4], pos = 1

輸出：傳回索引為 1 的連結清單節點

解釋：連結清單中有一個環，其尾部連接配接到第二個節點。

示例 2：

輸入：head = [1,2], pos = 0

輸出：傳回索引為 0 的連結清單節點

解釋：連結清單中有一個環，其尾部連接配接到第一個節點。

示例 3：

輸入：head = [1], pos = -1

輸出：傳回 null

解釋：連結清單中沒有環。

提示：

• 連結清單中節點的數目範圍在範圍 [0, 10^4] 内
• -10^5 <= Node.val <= 10^5
• pos 的值為 -1 或者連結清單中的一個有效索引

來源：力扣（LeetCode）

連結：​​​https://leetcode-cn.com/problems/linked-list-cycle-ii​​ 著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

二，解題思路

基于這一題​​@&再見螢火蟲&【LeetCode_LinkedList_141. Linked List Cycle 環形連結清單（C++/Java）【快慢指針】】​​

假設慢指針速度為1，快指針速度為2，從最一般的角度看，有如下規律：

慢指針slow經過路程a走到B點時，快指針fast經過2a走到C點，其中假設B點為環的起始點；

由于快指針比慢指針速度大一，是以經過x次移動後，兩指針相遇（假設慢指針不動，快指針相對速度為1，且快指針距離慢指針為x，故得出結論），由于每次慢指針移動一位，是以相遇時如圖：

是以，從相遇點D到環的起點B距離為a，等于起點A到B的距離；

也就是說，在相遇之後，将其中一個指針放在起點，另一個指針仍在相遇點（由于是離散模型，具體算法實作時可能有小偏差，比如相遇點指針需要向前移動一位才能保證再次相遇），移動相同距離後再次相遇，相遇點就是環的起點。

三，AC代碼

C++

/**
 * 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 == NULL || head->next == NULL) return NULL;
        ListNode *slow = head, *fast = head->next;
        while(fast->next != NULL && fast->next->next != NULL && fast != slow) {
            slow = slow->next;
            fast = fast->next->next;
        }
        if(slow != fast) return NULL;
        slow = head;
        fast = fast->next;
        while(slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
        
    }
};      

Java

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null) return null;
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast.next != null && fast.next.next != null && !(slow.equals(fast))) {
            slow = slow.next;
            fast = fast.next.next;
        }
        if(!(slow.equals(fast))) return null;
        slow =head;
        fast = fast.next;
        while(!(slow.equals(fast))) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}      

四，解題過程

第一博