问题描述:
给定一个链表, 返回链表开始入环的第一个节点. 如果链表无环, 则返回 null.
为了表示给定链表中的环, 我们使用整数 pos 来表示链表尾连接到链表中的位置 (索引从 0 开始). 如果 pos 是 -1, 则在该链表中没有环.
说明: 不允许修改给定的链表.
示例 1:
输入: head = [3,2,0,-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 head
- return None
结果:
来源: http://www.bubuko.com/infodetail-3429716.html