給定一個鏈表，判斷鏈表中是否有環(huán)。

為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該鏈表中沒有環(huán)。

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

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

示例 3：
輸入： head = [1], pos = -1
輸出： false
解釋： 鏈表中沒有環(huán)。

進階：
你能用 O(1)（即，常量）內(nèi)存解決此問題嗎？

題目分析：
這道題要求我們找出鏈表是否存在環(huán)。我們先考慮當鏈表無環(huán)時是怎樣的呢？如果一個鏈表無環(huán)，那么當我們從頭開始遍歷該鏈表到最后，每個點都只會被遍歷一次，并且結(jié)尾一定會存在一個空節(jié)點，標記我們的鏈表遍歷結(jié)束。那么當鏈表有環(huán)時，當我們遍歷該鏈表時，從鏈表中的某個點開始，這個環(huán)中的點會被反復遍歷。如示例1所示，從節(jié)點2開始，2,0,4節(jié)點被反復遍歷。既然有節(jié)點重復，我們的直觀想法就是建立一個哈希表，該表中存儲節(jié)點的地址，如果當?shù)刂吩谠摴１碇写嬖跁r就表明有重復節(jié)點出現(xiàn)，說明環(huán)存在。否則算法遍歷到鏈表末尾空節(jié)點結(jié)束。該算法只是遍歷鏈表所以時間復雜度為O(n)，n為鏈表的長度，因為我們額外建立了一張哈希表來存儲每一個節(jié)點的地址，所以空間復雜度也是O(n)。

在面試中一開始如果你說出了一個這樣的初始解法，都會給面試官一個還算靠譜的印象。但這道題作為一道簡單題，面試官聽了你的上述思路后并不會急于讓你實現(xiàn)，而是會期望你給出一個空間復雜度為O(1)的解法，也就是本題的進階要求。

本題我們還是可以繼續(xù)使用鏈表題目中常見的快慢指針這一解題思路來進行解答。我們平時在繞著操場跑步時都有過這樣的體驗，有的人跑的很快，而自己跑的很慢，那么跑的快的那個人就會在某個時刻趕上或者超過我們。那么這里也是同樣的，我們的慢指針每次只走一步，快指針每次走兩步，如果鏈表沒有環(huán)，快指針率先遍歷完鏈表到達鏈表末尾。如果鏈表有環(huán)，那么在某個點快慢指針一定會相遇（即快慢指針有一樣的地址），相遇時我們就可以說鏈表中存在環(huán)了。這里我們只用了快慢指針的額外存儲空間，所以我們的空間復雜度就是O(1)。
其實計算機科學家們已經(jīng)對此類環(huán)探測問題設(shè)計了相應的理論和算法，我們上述的描述的形式化算法描述叫做Floyd Cycle Detection（佛洛依德環(huán)檢測算法），有興趣的同學可以在網(wǎng)絡上搜索相應資料深入了解一下。

有了上述的想法，其實代碼寫出來就很直接了，下面給出5種語言的實現(xiàn)。
c++實現(xiàn)

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

Go語言實現(xiàn)

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return false
    }

    var slow *ListNode = head
    var fast *ListNode = head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            return true
        }
    }

    return false
}

Java實現(xiàn)

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

C#實現(xiàn)

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

Python實現(xiàn)

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def hasCycle(self, head):
        if head == None or head.next == None:
            return False
        slow = head
        fast = head
        while fast != None and fast.next != None:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

最后也請大家想一下，如果我們想把環(huán)的第一個節(jié)點找出來，我們還需要怎么設(shè)計我們的算法呢？