C++怎么解決單鏈表中的環問題

本文小編為大家詳細介紹“C++怎么解決單鏈表中的環問題”，內容詳細，步驟清晰，細節處理妥當，希望這篇“C++怎么解決單鏈表中的環問題”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學習新知識吧。

單鏈表中的環

Example 1:

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

Output: true

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

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Follow up:

Can you solve it using O(1) (i.e. constant) memory?

這道題是快慢指針的經典應用。只需要設兩個指針，一個每次走一步的慢指針和一個每次走兩步的快指針，如果鏈表里有環的話，兩個指針最終肯定會相遇。實在是太巧妙了，要是我肯定想不出來。代碼如下：

C++ 解法：

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) return true;
        }
        return false;
    }
};

Java 解法：

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
}

讀到這里，這篇“C++怎么解決單鏈表中的環問題”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注億速云行業資訊頻道。