問題描述

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

leetcode原題鏈接

問題分析

樸素思維：從頭遍歷鏈表，每遍歷到一個(gè)節(jié)點(diǎn)記錄下來（采用map），遍歷新節(jié)點(diǎn)時(shí)發(fā)現(xiàn)map中已經(jīng)存在，證明鏈表中存在環(huán)。
跳躍思維：采用兩個(gè)指針來遍歷鏈表，fast一次跳躍兩個(gè)節(jié)點(diǎn)，slow一次跳躍一個(gè)節(jié)點(diǎn)，fast指針先跳，兩個(gè)指針如果相遇，證明鏈表中存在環(huán)。

快慢指針空間復(fù)雜度為O(1)，我們重點(diǎn)分析下快慢指針解法：

• fast一次跳躍兩個(gè)節(jié)點(diǎn)，slow一次跳躍一個(gè)節(jié)點(diǎn)，需特別注意fast的空指針問題。
• fast、slow指針以哪種方式相遇？這個(gè)如果梳理不清楚，代碼很容易出錯(cuò)。由于環(huán)的位置不確定，快慢指針相遇可能是slow追上fast相遇（fast在環(huán)內(nèi)，slow由環(huán)外進(jìn)入環(huán)內(nèi)），也可能是fast追上slow相遇。
  • 相遇的方式

    相遇方式1：slow領(lǐng)先fast一個(gè)位置，fast跳躍一次后相遇。
    相遇方式2：slow領(lǐng)先fast兩個(gè)位置，fast跳躍兩次后相遇。
    相遇方式3：fast領(lǐng)先slow一個(gè)位置，slow跳躍一次后相遇。
    - 寫代碼時(shí)考慮這三種相遇方式太復(fù)雜了，三種相遇方式是否可以統(tǒng)一轉(zhuǎn)變成一種呢？
    > 轉(zhuǎn)化相遇方式1：slow領(lǐng)先fast一個(gè)位置，fast跳躍一次后相遇（此時(shí)不終止），fast完成第二次跳躍，此時(shí)fast領(lǐng)先slow一個(gè)位置，相遇方式1轉(zhuǎn)變成了相遇方式3。
    > 轉(zhuǎn)化相遇方式2：slow領(lǐng)先fast兩個(gè)位置，fast跳躍兩次后相遇（此時(shí)不終止），slow繼續(xù)跳躍一次，此時(shí)slow領(lǐng)先fast一個(gè)位置，相遇方式2轉(zhuǎn)變成了相遇方式1，可以由相遇方式1轉(zhuǎn)變?yōu)橄嘤龇绞?。

解題思路

問題拆解是解決問題的一個(gè)非常重要的原則。此題的拆解如下：

1. 跳躍：fast跳躍兩次，slow跳躍一次。然后判斷fast，slow是否相等。
2. 循環(huán)跳躍。

   循環(huán)進(jìn)行條件：fast不為空，fast.next不為空。
   循環(huán)終止條件：fast為空或者fast.next為空（無環(huán)）、fast和slow跳躍后，fast等于slow（有環(huán)）

代碼示例1 （python）

# 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):
        """
        :type head: ListNode
        :rtype: bool
        """
        fast = head
        slow = head
        while fast != None and fast.next != None:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return True
        return False

思想總結(jié)

• 無論何時(shí)，指針使用前都要保證非空。
• 將問題的多種情況進(jìn)行轉(zhuǎn)化統(tǒng)一，只解決一種情況會(huì)簡(jiǎn)單很多。