給定一個鏈表，判斷鏈表中是否有環(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)蹂匹。我們先考慮當(dāng)鏈表無環(huán)時是怎樣的呢碘菜？如果一個鏈表無環(huán)，那么當(dāng)我們從頭開始遍歷該鏈表到最后，每個點都只會被遍歷一次，并且結(jié)尾一定會存在一個空節(jié)點胡桨，標(biāo)記我們的鏈表遍歷結(jié)束。那么當(dāng)鏈表有環(huán)時计雌，當(dāng)我們遍歷該鏈表時，從鏈表中的某個點開始静尼，這個環(huán)中的點會被反復(fù)遍歷白粉。如示例1所示，從節(jié)點2開始鼠渺，2,0,4節(jié)點被反復(fù)遍歷鸭巴。既然有節(jié)點重復(fù)，我們的直觀想法就是建立一個哈希表拦盹，該表中存儲節(jié)點的地址鹃祖，如果當(dāng)?shù)刂吩谠摴１碇写嬖跁r就表明有重復(fù)節(jié)點出現(xiàn)，說明環(huán)存在普舆。否則算法遍歷到鏈表末尾空節(jié)點結(jié)束恬口。該算法只是遍歷鏈表所以時間復(fù)雜度為O(n)校读，n為鏈表的長度，因為我們額外建立了一張哈希表來存儲每一個節(jié)點的地址祖能，所以空間復(fù)雜度也是O(n)歉秫。
在面試中一開始如果你說出了一個這樣的初始解法，都會給面試官一個還算靠譜的印象养铸。但這道題作為一道簡單題雁芙，面試官聽了你的上述思路后并不會急于讓你實現(xiàn)，而是會期望你給出一個空間復(fù)雜度為O(1)的解法钞螟，也就是本題的進階要求兔甘。
本題我們還是可以繼續(xù)使用鏈表題目中常見的快慢指針這一解題思路來進行解答。我們平時在繞著操場跑步時都有過這樣的體驗鳞滨，有的人跑的很快洞焙，而自己跑的很慢，那么跑的快的那個人就會在某個時刻趕上或者超過我們拯啦。那么這里也是同樣的澡匪，我們的慢指針每次只走一步，快指針每次走兩步褒链，如果鏈表沒有環(huán)仙蛉，快指針率先遍歷完鏈表到達鏈表末尾。如果鏈表有環(huán)碱蒙，那么在某個點快慢指針一定會相遇（即快慢指針有一樣的地址），相遇時我們就可以說鏈表中存在環(huán)了夯巷。這里我們只用了快慢指針的額外存儲空間赛惩，所以我們的空間復(fù)雜度就是O(1)。
其實計算機科學(xué)家們已經(jīng)對此類環(huán)探測問題設(shè)計了相應(yīng)的理論和算法趁餐，我們上述的描述的形式化算法描述叫做Floyd Cycle Detection（佛洛依德環(huán)檢測算法）喷兼，有興趣的同學(xué)可以在網(wǎng)絡(luò)上搜索相應(yī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è)計我們的算法呢？
