【python-leetcode142-快慢指针】环形链表2

发布时间：2020-12-20 09:54:52 所属栏目：Python 来源：网络整理

导读：问题描述：给定一个链表，返回链表开始入环的第一个节点。?如果链表无环，则返回?null。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。说明：不允许修改给定的链表

问题描述：

给定一个链表，返回链表开始入环的第一个节点。?如果链表无环，则返回?null。

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

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

示例 1：

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

核心：在leetcode141中已经解决了判断是否有环，这题是上一题的升级版本，需要求解出环的入口。当快指针和慢指针第一次相遇时，让快指针重新指向头结点，并规定此时快指针和慢指针的步伐是一致的，此时当他们再次相遇时，该节点就是入口了。

# Definition for singly-linked list.
# class ListNode:     def __init__(self,x):         self.val = x         self.next = None

class Solution:
    def detectCycle(self,head: ListNode) -> ListNode:
        if head == None or head.next == None:
            return None
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                while head != slow:
                    head = head.next
                    slow = slow.next
                return None

结果：

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!