题目 1
题目原文
给定一个链表,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪next
指针再次到达,则链表中存在环。
为了表示给定链表中的环,我们使用整数pos
来表示链表尾连接到链表中的位置(索引从 0 开始)。
如果pos
是 ,则在该链表中没有环。
注意:pos
不作为参数进行传递,仅仅是为了标识链表的实际情况。
如果链表中存在环,则返回true
。否则,返回false
。
进阶:
你能用 O(1)(即,常量)内存解决此问题吗?
如果链表中有某个节点,可以通过连续跟踪next
指针再次到达,则链表中存在环。
为了表示给定链表中的环,我们使用整数pos
来表示链表尾连接到链表中的位置(索引从 0 开始)。
如果pos
是 ,则在该链表中没有环。
注意: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
复杂度分析:
时间复杂度:
空间复杂度:
可见该方法的空间复杂度较高,利用双指针方法可以不增加哈希表的额外空间。
双指针-快慢指针
该方法的思想很简单,设置一个快指针,一次走两步,一个慢指针,一次只走一步。若存在环,由于快指针比慢指针快,所以一定会追上慢指针。
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
复杂度分析:
时间复杂度:。
空间复杂度:。只是用了两个指针的额外空间。
双指针-修改链表
换个角度,在允许修改链表的情况下,我们可以对链表进行修改,进而也可以不需要额外空间,判断链表是否存在环。
思路如下:
在遍历链表的同时,修改每个节点的值,或者修改链表结构,使得每个节点的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,则在该链表中没有环。
说明:不允许修改给定的链表。
为了表示给定链表中的环,我们使用整数 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
复杂度分析:
时间复杂度:。N为节点数。
空间复杂度:。最坏情况下遍历所有节点才能找到环。
双指针-快慢指针
首先,我们将有环链表分成3部分,如下图的a,b,c:
假设,慢指针在走到图中紫色点时,快指针已经走了环的n圈,那么快指针所走的距离为:
由快慢指针的速度可知,快指针是慢指针速度的二倍,走的距离也是慢指针的二倍,所以得到如下关系:
由上式可知,从头结点到入环点的距离,正好等于从相遇点到入环点的距离加上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