Skip to content

Latest commit

 

History

History
128 lines (109 loc) · 3.9 KB

141. 环形链表-Easy.md

File metadata and controls

128 lines (109 loc) · 3.9 KB

Description

给定一个链表，判断链表中是否有环。

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

如果链表中存在环，则返回 true 。 否则，返回 false 。

进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

 

示例 1：

![[Pasted image 20201009215120.png]]

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2： ![[Pasted image 20201009215138.png]]

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3： ![[Pasted image 20201009215143.png]]

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

链表中节点的数目范围是 [0, 104] -105 <= Node.val <= 105 pos 为 -1 或者链表中的一个 有效索引 。

Solution

1. 我的解法（快慢指针，空间复杂度O(1)，简洁性存在优化空间）

  • 快慢指针思路较为简单，就不赘述了
  • 我的code在一个iteration里面完成了快指针走两步，慢指针走一步的操作，因此代码比较冗余；可参考题解中，慢指针2个iteration走一步的设定
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head:
            return False
        else:
            fast = head
            slow = head
            flag = True
            while fast != slow or flag:
                if fast:
                    fast = fast.next
                if fast:
                    fast = fast.next
                slow = slow.next
                flag = False

            if not fast:
                return False
            else:
                return True

2. 题解思路

1. 快慢指针（简洁版）

  • 以while fast（快指针是否走完）作为循环条件，在常数上减少iteration次数
class Solution:
    def hasCycle(self, head: ListNode) -> ListNode:
        fast, slow = head, head
        while True:
            if not (fast and fast.next): return False
            fast, slow = fast.next.next, slow.next
            if fast == slow: break
        fast = head
        while fast != slow:
            fast, slow = fast.next, slow.next
        return True

2. 链表反转（空间复杂度O(1)，变更原链表结构）【有点妙】

  • 按顺序反转链表，由于环之前的部分已经反转，最后会返回到head节点，空间复杂度为O(1)
class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        # 4. 列表倒置
        if not head or not head.next:
            return False
        p, q = None, head
        while q:
            u, p, q = p, q, q.next
            p.next = u
        return head == q

3. 将val标记为特殊值

  • 将原链表val值变为特殊值，若访问的节点val已经被变更过就是有环 python中可以给节点添加新属性不改变原链表，则空间复杂度变为O(n)
class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        # 5. 标记val
        while head:
            # s = getattr(head, 's', None)  # 获取s属性
            # if s:  # 判断s属性
            if head.val == '1':
                return True
            # head.s = 1  # 添加s属性
            head.val = '1'
            head = head.next
        return False