給定一個(gè)鏈表洼滚，返回鏈表開始入環(huán)的第一個(gè)節(jié)點(diǎn)速梗。 如果鏈表無環(huán)枚碗，則返回 null钞啸。
為了表示給定鏈表中的環(huán)几蜻，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1体斩，則在該鏈表中沒有環(huán)梭稚。
說明：不允許修改給定的鏈表。
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Note: Do not modify the linked list.
示例 1：
輸入：head = [3,2,0,-4], pos = 1
輸出：tail connects to node index 1
解釋：鏈表中有一個(gè)環(huán)絮吵，其尾部連接到第二個(gè)節(jié)點(diǎn)弧烤。
示例 2：
輸入：head = [1,2], pos = 0
輸出：tail connects to node index 0
解釋：鏈表中有一個(gè)環(huán)，其尾部連接到第一個(gè)節(jié)點(diǎn)蹬敲。
示例 3：
輸入：head = [1], pos = -1
輸出：no cycle
解釋：鏈表中沒有環(huán)暇昂。
進(jìn)階： 你是否可以不用額外空間解決此題？
Follow-up: Can you solve it without using extra space?
解題思路：
和上一道題比只多了一步判斷入環(huán)節(jié)點(diǎn)在哪伴嗡。兩種方法：
哈希表：
哈希表添加節(jié)點(diǎn)時(shí)只要發(fā)現(xiàn)節(jié)點(diǎn)已經(jīng)存在了急波，證明就有環(huán)形鏈表。并且已存在的節(jié)點(diǎn)即為入環(huán)節(jié)點(diǎn)
雙指針：
畫了個(gè)圖幫助理解：
一快一慢雙指針開始從頭結(jié)點(diǎn)遍歷鏈表瘪校，快節(jié)點(diǎn)速度為2澄暮，慢節(jié)點(diǎn)速度為1：
相遇時(shí)：
慢節(jié)點(diǎn)走了：a+b
由于快指針?biāo)俣仁锹羔樀?倍，快節(jié)點(diǎn)走了：2(a+b)
快慢節(jié)點(diǎn)相遇時(shí)快節(jié)點(diǎn)比慢節(jié)點(diǎn)剛好多走了一圈環(huán)形節(jié)點(diǎn)渣淤∩涂埽快節(jié)點(diǎn)走了：(a+b)+(b+c)
列方程：2(a+b)=(a+b)+(b+c)
解得 a=c
也就是說：相遇節(jié)點(diǎn)到入環(huán)節(jié)點(diǎn)的長度和頭節(jié)點(diǎn)到入環(huán)節(jié)點(diǎn)的長度相等
可以得出結(jié)論吉嫩，如果此時(shí)讓慢節(jié)點(diǎn)或快節(jié)點(diǎn)中的一個(gè)指向頭節(jié)點(diǎn)价认，另一個(gè)留在相遇節(jié)點(diǎn)，然后速度都為1自娩，繼續(xù)遍歷鏈表用踩，雙指針再次相遇時(shí)的節(jié)點(diǎn)剛好是入環(huán)節(jié)點(diǎn)渠退。
注：為了理解方便，把長度 b 定為上半部分長度脐彩，實(shí)際上 b 應(yīng)該為快慢節(jié)點(diǎn)相遇時(shí)慢節(jié)點(diǎn)繞過環(huán)形鏈表的總長度
哈希表解題：
Java：
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null) return null;//如果是空鏈表直接返回
Set<ListNode> nodeSet = new HashSet<>();//構(gòu)造哈希表
while (head.next != null) {//鏈表下一個(gè)不為空
if (nodeSet.contains(head)) return head;//哈希表包含該節(jié)點(diǎn)則存在環(huán)形鏈表
nodeSet.add(head);//加入節(jié)點(diǎn)
head = head.next;//下移一位
}
return null;
}
}
Python：
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None:
return None
hashSet=set()#構(gòu)造集合
while(head.next is not None):
if head in hashSet:#是否已存在
return head
hashSet.add(head)
head=head.next
return None
雙指針解題：
Java：
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) {
return null;
}
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {//快指針及其下一位是否為null
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {//如果相同碎乃，存在環(huán)形鏈表
slow = head;//指向頭節(jié)點(diǎn)
while (slow != fast) {//繼續(xù)遍歷，再次相遇時(shí)的節(jié)點(diǎn)即為入環(huán)節(jié)點(diǎn)
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
}
Python：
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None or head.next is None:
return None
slow, fast = head, head
while fast is not None and fast.next is not None:
slow, fast = slow.next, fast.next.next
if slow == fast:
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
return None
歡迎關(guān)注公眾號(hào)：愛寫B(tài)ug（ID：iCodeBugs）
