有關(guān)鏈表的LeetCode做題筆記合集镜遣，Python實(shí)現(xiàn)
鏈表定義
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
142. 環(huán)形鏈表 II Linked List Cycle II
第一種方法還是上面的用哈希表set來記錄，占用空間
class Solution(object):
# 1.set記錄
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
rec = []
curr = head
while curr:
if curr in rec:
return rec[rec.index(curr)]
rec.append(curr)
curr = curr.next
return None
第二種方法用快慢指針心铃，先如上題一樣檢測(cè)是否有環(huán)捣郊，有的話設(shè)置一個(gè)新的檢測(cè)節(jié)點(diǎn)從頭(head)開始迭代训裆，同時(shí)slow節(jié)點(diǎn)也繼續(xù)迭代抱慌，直到二者相遇的點(diǎn)就是環(huán)的入口節(jié)點(diǎn)霜威。
原理：
首先酪刀，頭結(jié)點(diǎn)到入環(huán)結(jié)點(diǎn)的距離為a，入環(huán)結(jié)點(diǎn)到相遇結(jié)點(diǎn)的距離為b钮孵，相遇結(jié)點(diǎn)到入環(huán)結(jié)點(diǎn)的距離為c骂倘。然后，當(dāng)f以s的兩倍速度前進(jìn)并和s相遇時(shí)油猫，f走過的距離是s的兩倍稠茂，即有等式：a+b+c+b = 2(a+b) 柠偶，可以得出 a = c 情妖，所以說，讓fast和slow分別從相遇結(jié)點(diǎn)和頭結(jié)點(diǎn)同時(shí)同步長(zhǎng)出發(fā)诱担，他們的相遇結(jié)點(diǎn)就是入環(huán)結(jié)點(diǎn)毡证。
當(dāng)快、慢指針同時(shí)從入環(huán)點(diǎn)出發(fā)蔫仙，那么一定會(huì)在入環(huán)點(diǎn)相遇料睛。如果快、慢指針同時(shí)從入環(huán)點(diǎn)前一節(jié)點(diǎn)出發(fā)摇邦，那么快慢恤煞、指針則會(huì)在入環(huán)點(diǎn)的前一節(jié)點(diǎn)相遇，以此類推施籍。
class Solution(object):
# 2.快慢指針
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
slow = fast = head
while slow and fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
detection = head
while slow != detection:
slow = slow.next
detection = detection.next
return detection
return None
