【算法日常】判斷環形鏈表

環形鏈表

題目來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/linked-list-cycle-ii

目前考慮到兩種解法，但都需要輔助空間， 第一種 O(n) 第二種 O(1)

第一種 借助輔助字典進行判斷

將走過的節點都記錄在字典中，通過查詢字典的key值是否存在來確定是否有環
時間復雜度為 O(n) , 空間復雜度為 O(n)

代碼如下：

# -*- coding: utf-8 -*-
# @Author   : xaohuihui
# @Time     : 19-12-9
# @File     : detect_cycled_ii.py
# Software  : study

"""
環形鏈表ii
"""

class ListNode:
    def __init__(self, x):
        self.x = x
        self.next = None

# Number.1
def has_cycle(head: ListNode) -> ListNode:
    result = None
    if head and head.next:
        set_node = set()
        while head:
            if head in set_node:
                result = head
                break
            set_node.add(head)
            head = head.next
    return result

if __name__ == '__main__':
    # head=[3,2,0,4] pos= 1
    node1 = ListNode(3)
    node2 = ListNode(2)
    node3 = ListNode(0)
    node4 = ListNode(4)

    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node2

    result_node = has_cycle(node1)
    if result_node:
        start = node1
        i = 0
        while start:
            if result_node == start:
                print(f"tail connects to node index {i}")
                break
            i += 1
            start = start.next
    else:
        print("no cycle")

輸出如下：

tail connects to node index 1

第二種解法 快慢指針

使用快慢指針，快指針每次走兩步，慢指針每次走一步。
如果單鏈表中有環，快慢指針肯定會相遇，如圖a.所示，在相遇后，將快指針指向開始位置，結束第一次循環。
第二次循環，將快指針變為沒次走一步，慢指針每次走一步，如圖b.所示，如果再次相遇，該點就為環點
時間復雜度為 O(n) , 空間復雜度為 O(1)
特別注意： 若環點就在起始節點，第一次快慢指針相遇一定在環點 ，則fast和slow此時都指向起始節點，則第二次循環不必執行，如圖c.所示

圖a.

圖b.

圖c.

代碼如下：

# -*- coding: utf-8 -*-
# @Author   : xaohuihui
# @Time     : 19-12-9
# @File     : detect_cycled_ii.py
# Software  : study

"""
環形鏈表ii
"""

class ListNode:
    def __init__(self, x):
        self.x = x
        self.next = None

# NUmber.2
def has_cycle(head: ListNode) -> ListNode:
    result = None
    if head and head.next:
        fast = slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                fast = head
                break
        else:
            return result

        while fast != slow:
            fast = fast.next
            slow = slow.next
        result = fast
    return result

if __name__ == '__main__':
    # head=[3,2,0,4] pos= 0
    node1 = ListNode(3)
    node2 = ListNode(2)
    node3 = ListNode(0)
    node4 = ListNode(4)

    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node1

    result_node = has_cycle(node1)
    if result_node:
        start = node1
        i = 0
        while start:
            if result_node == start:
                print(f"tail connects to node index {i}")
                break
            i += 1
            start = start.next
    else:
        print("no cycle")

輸出結果

tail connects to node index 0