题目 1

题目链接

题目原文 给定一个链表,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪next指针再次到达,则链表中存在环。
为了表示给定链表中的环,我们使用整数pos来表示链表尾连接到链表中的位置(索引从 0 开始)。
如果pos1-1,则在该链表中没有环。
注意:pos不作为参数进行传递,仅仅是为了标识链表的实际情况。

如果链表中存在环,则返回true。否则,返回false
进阶:

你能用 O(1)(即,常量)内存解决此问题吗?

示例示例

题目解析

该题仅需要判断链表中是否存在环,如果存在则返回True。很容易可以想到利用哈希表来存储已经遍历过节点的父节点,若发现某个节点存在两个父节点,则一定存在环。此外,我们可以利用双指针法来避免引入额外空间。

解题方法

哈希表

对于python我们可以将已经遍历过的节点放入set中,如果遍历过即返回True。

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        # 已访问过的节点集合
        visited = set([])
        ptr = head
        while ptr is not None:
            if ptr in visited:
                return True
            visited.add(ptr)
            ptr=ptr.next
        return False

复杂度分析:
时间复杂度:O(N)O(N)
空间复杂度:O(N)O(N)
可见该方法的空间复杂度较高,利用双指针方法可以不增加哈希表的额外空间。

双指针-快慢指针

该方法的思想很简单,设置一个快指针,一次走两步,一个慢指针,一次只走一步。若存在环,由于快指针比慢指针快,所以一定会追上慢指针。

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        # 快慢指针
        fast = head
        slow = head
        while fast is not None:
            slow = slow.next
            fast = fast.next
            if fast is None:
                return False
            fast = fast.next
            if slow == fast:
                # 两指针相遇,存在环
                return True

复杂度分析:
时间复杂度:O(N)O(N)
空间复杂度:O(1)O(1)。只是用了两个指针的额外空间。

双指针-修改链表

换个角度,在允许修改链表的情况下,我们可以对链表进行修改,进而也可以不需要额外空间,判断链表是否存在环。
思路如下:
在遍历链表的同时,修改每个节点的值,或者修改链表结构,使得每个节点的next指针指向自身,构建一个小环
此外,使用两个速度相同的指针,在遍历过程中修改链表。当遇到某个节点的next指向自身时,则发现环。

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        # 双指针
        first_point = head
        second_point = head
        # 每个节点遍历后指向自身
        while True:
            if first_point is None:
                return False
            if first_point == first_point.next:
                # 找到环 
                return True
            first_point = first_point.next
            second_point.next = second_point
            second_point = first_point

题目2

题目链接

题目原文 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

说明:不允许修改给定的链表。

题目解析

需要注意的是,本题不允许修改链表,并且需要给出开始入环的第一个节点。对于哈希表方法来说,修改十分简单,但是对于快慢指针,需要分析快慢指针的关系,进而计算快慢指针相遇时与入环点的距离。

解题方法

哈希表

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        # 已访问过的节点集合
        visited = set([])
        ptr = head
        while ptr is not None:
            if ptr in visited:
                return ptr
            visited.add(ptr)
            ptr=ptr.next
        return None

复杂度分析:
时间复杂度:O(N)O(N)。N为节点数。
空间复杂度:O(N)O(N)。最坏情况下遍历所有节点才能找到环。

双指针-快慢指针

首先,我们将有环链表分成3部分,如下图的a,b,c:

有环链表简化图有环链表简化图

假设,慢指针在走到图中紫色点时,快指针已经走了环的n圈,那么快指针所走的距离为:
a+n(b+c)+b=a+(n+1)b+c a+n(b+c)+b = a + (n+1)b + c
由快慢指针的速度可知,快指针是慢指针速度的二倍,走的距离也是慢指针的二倍,所以得到如下关系:
a+(n+1)b+c=2(a+b)a=(n1)b+c a + (n+1)b + c = 2(a+b) \\ a = (n-1)b + c
由上式可知,从头结点到入环点的距离,正好等于从相遇点到入环点的距离加上n-1圈的环长。
因此,当快慢指针相遇时,我们可以再用一个额外指针,从头指针开始向后遍历,慢指针同时向后遍历,他们最终会在入环点相遇。

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        # 快慢指针
        fast = head
        slow = head
        ptr = None
        while fast is not None:
            slow = slow.next
            fast = fast.next
            if fast is None:
                return None
            fast = fast.next
            if slow == fast:
                # 快慢指针相遇
                ptr = head
                while slow != ptr:
                    slow = slow.next
                    ptr = ptr.next
                break
        return ptr

参考

https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode-solution/