LeetCode.jpg

目錄鏈接：http://www.itdecent.cn/p/9c0ada9e0ede

環(huán)形鏈表

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

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

示例 1：

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

image

示例 2：

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

image

示例 3：

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

image

切題

一、Clarification
本題沒(méi)有什么需要注意的邊界條件，目標(biāo)也很簡(jiǎn)單判斷鏈表是否成環(huán)

二、Possible Solution

1、存儲(chǔ)記錄
這應(yīng)該是比較容易想到的，將我們遍歷的節(jié)點(diǎn)記錄下來(lái)，然后每次新節(jié)點(diǎn)都看它是否已經(jīng)被記錄，如果沒(méi)有就將其記錄下來(lái)，如果有表示鏈表成環(huán)，如果到了鏈表末尾到?jīng)]有重復(fù)記錄表示鏈表沒(méi)有環(huán)
python的話可以用set來(lái)記錄節(jié)點(diǎn)，其時(shí)間復(fù)雜度為 O(n)

2、快慢指針
兩個(gè)指針循環(huán)遍歷鏈表，慢指針每次循環(huán)移一步快指針每次循環(huán)移兩步，如果鏈表遍歷結(jié)束之前存在快慢指針指向同一節(jié)點(diǎn)則鏈表成環(huán),如果快或慢指針到達(dá)鏈表結(jié)尾且沒(méi)相遇表示鏈表無(wú)環(huán)，其時(shí)間復(fù)雜度為 O(n)

Python3 實(shí)現(xiàn)

1、存儲(chǔ)記錄 實(shí)現(xiàn) Py3

環(huán)形鏈表(Linked List Cycle) Py3 存儲(chǔ)記錄 實(shí)現(xiàn)

# @author:leacoder
# @des:  存儲(chǔ)記錄 環(huán)形鏈表

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        save = set() #用于 存儲(chǔ) 鏈表中每個(gè)節(jié)點(diǎn)地址
        cur = head
        while cur is not None: #循環(huán)迭代鏈表
            if cur in save: #是否有記錄
                return True #有返回True
            else:
                save.add(cur) #存儲(chǔ)記錄cur
                cur = cur.next #下移
        return False

2、快慢指針 實(shí)現(xiàn) Py3

環(huán)形鏈表(Linked List Cycle) Py3 快慢指針 實(shí)現(xiàn)

# @author:leacoder
# @des:  快慢指針 環(huán)形鏈表

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        fast = slow = head
        while fast.next:
            slow = slow.next  #慢指針 每次移一步
            fast = fast.next.next #快指針 每次移二步
            if slow == fast: 
                return True
        return False

Java實(shí)現(xiàn)

Java實(shí)現(xiàn)邏輯上與Python3無(wú)區(qū)別

1、存儲(chǔ)記錄 實(shí)現(xiàn) Java

環(huán)形鏈表(Linked List Cycle) Java 存儲(chǔ)記錄 實(shí)現(xiàn)

2、快慢指針 實(shí)現(xiàn) Java

環(huán)形鏈表(Linked List Cycle) Java 快慢指針 實(shí)現(xiàn)

C++實(shí)現(xiàn)

環(huán)形鏈表(Linked List Cycle) C++ 快慢指針 實(shí)現(xiàn)

擴(kuò)展閱讀：

Python3 集合
Python Data Structures
Java 集合框架
Java HashSet api doc from oracle
HashSet 的實(shí)現(xiàn)原理

GitHub鏈接：
https://github.com/lichangke/LeetCode

知乎個(gè)人首頁(yè)：
https://www.zhihu.com/people/lichangke/

簡(jiǎn)書(shū)個(gè)人首頁(yè)：
http://www.itdecent.cn/u/3e95c7555dc7

個(gè)人Blog:
https://lichangke.github.io/

歡迎大家來(lái)一起交流學(xué)習(xí)