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

目錄

​​一，題目描述​​

​​英文描述​​

​​中文描述​​

​​二，解題思路​​

​​三，AC代碼​​

​​C++​​

​​Java​​

​​四，解題過程​​

​​第一博​​

一，題目描述

英文描述

Given head, the head of a linked list, determine if the linked list has a cycle in it.

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.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

Input: head = [3,2,0,-4], pos = 1 Output: true

Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0 Output: true

Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1 Output: false

Explanation: There is no cycle in the linked list.

Constraints:

• The number of the nodes in the list is in the range [0, 10^4].
• -10^5 <= Node.val <= 10^5
• pos is -1 or a valid index in the linked-list.

中文描述

給定一個連結清單，判斷連結清單中是否有環。

如果連結清單中有某個節點，可以通過連續跟蹤 next 指針再次到達，則連結清單中存在環。 為了表示給定連結清單中的環，我們使用整數 pos 來表示連結清單尾連接配接到連結清單中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該連結清單中沒有環。注意：pos 不作為參數進行傳遞，僅僅是為了辨別連結清單的實際情況。

如果連結清單中存在環，則傳回 true 。 否則，傳回 false 。

進階：

你能用 O(1)（即，常量）記憶體解決此問題嗎？

示例 1：

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

輸出：true

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

來源：力扣（LeetCode）

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

二，解題思路

首先有以下幾個直覺的事實：

• 1，如果一個連結清單是循環連結清單，由于連結清單的唯一指向性，那麼一個指針在前進過程中必定會進入一個循環，即永遠不會指向空指針；
• 2，當兩個指針以不同的速度進入循環後，會成為一個追及問題（假設指針靜止，快指針以速度差向前運動，快指針必定可以追上慢指針）。從離散的角度來看，速度相差為一時，快指針必定可以和慢指針位置重合；

三，AC代碼

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head == NULL || head->next == NULL) return false;
        ListNode *slow = head, *fast = head->next;
        while(fast->next != NULL && fast->next->next != NULL && slow != fast) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow == fast;
        
    }
};      

Java

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null) return false;
        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;
        }
        return slow.equals(fast);
    }
}      

四，解題過程

第一博