LeetCode.jpg

142. 環(huán)形鏈表 II

給定一個(gè)鏈表，返回鏈表開始入環(huán)的第一個(gè)節(jié)點(diǎn)酝静。 如果鏈表無環(huán)骄蝇，則返回 null。

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

說明：不允許修改給定的鏈表抖单。

示例 1：

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

示例 1.png

示例 2：

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

示例 2.png

示例 3：

輸入：head = [1], pos = -1
輸出：no cycle
解釋：鏈表中沒有環(huán)刃永。

示例 3.png

切題

一货矮、Clarification

注意鏈表位置索引從0開始

二、Possible Solution

1斯够、哈希表

set存儲(chǔ)記錄所有節(jié)點(diǎn)囚玫，如果下一節(jié)點(diǎn)在set中有那么此節(jié)點(diǎn)就是入環(huán)的第一個(gè)節(jié)點(diǎn)；如果直到鏈表結(jié)尾都沒有重復(fù)節(jié)點(diǎn)雳刺，表示無環(huán)劫灶，注意最后的None要提前放入set中。時(shí)間復(fù)雜度O(n)掖桦，空間復(fù)雜度O(n)

2本昏、快慢指針

參考 141通過快慢指針，slow每次移動(dòng)1枪汪，fast每次移動(dòng)2涌穆，可以找到他們相遇時(shí)的節(jié)點(diǎn)假設(shè)為meetnode，入環(huán)的第一個(gè)節(jié)點(diǎn)假設(shè)為firstnode,如下圖雀久。由于slow每次移動(dòng)1宿稀，fast每次移動(dòng)2，可知道head->firstnode->meetnode的節(jié)點(diǎn)個(gè)數(shù) = meetnode->firstnode->meetnode的節(jié)點(diǎn)個(gè)數(shù)赖捌，除去中間相同的一部分head->firstnode的節(jié)點(diǎn)個(gè)數(shù) = meetnode->firstnode的節(jié)點(diǎn)個(gè)數(shù)祝沸。 時(shí)間復(fù)雜度O(n)矮烹，空間復(fù)雜度O(1)

image.png

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

哈希表

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
# @author:leacoder 
# @des:  哈希表 環(huán)形鏈表 II

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        nodes = set()
        nodes.add(None)
        cur = head
        while cur not in nodes:
            nodes.add(cur)
            cur = cur.next
        return cur

快慢指針

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
# @author:leacoder 
# @des:  快慢指針 環(huán)形鏈表 II

class Solution(object):

    def getmeetnode(self,head):
        fast = slow = head
        while slow and fast and fast.next:
            slow = slow.next  #慢指針 每次移一步
            fast = fast.next.next #快指針 每次移二步
            if slow == fast: 
                return slow # 找出相遇節(jié)點(diǎn)
        return None # 沒有表示沒有成環(huán)，返回None

    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None:
            return None
        meetnode = self.getmeetnode(head)  # 找到 相遇時(shí)的節(jié)點(diǎn)meetnode
        if meetnode is None:  # 如果為None 表示不成環(huán)
            return None
        # 成環(huán) 由于 head->firstnode的節(jié)點(diǎn)個(gè)數(shù) = meetnode->firstnode的節(jié)點(diǎn)個(gè)數(shù)
        cur1 ,cur2 = head,meetnode
        while cur1!=cur2:
            cur1,cur2 = cur1.next,cur2.next
        return cur1

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

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

簡書個(gè)人首頁：
http://www.reibang.com/u/3e95c7555dc7

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

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