【Leetcode】142.环形链表II-Toy模板网

这篇具有很好参考价值的文章主要介绍了【Leetcode】142.环形链表II。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

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

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

一开始我是这么写的

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

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        dummy_head = ListNode(next=head)
        fast = dummy_head.next.next
        slow = dummy_head
        len = 0

        while fast and slow:
            if fast == slow :
                return fast
            fast = fast.next.next
            print(fast.val)
            slow = slow.next
            print(slow.val)
            len += 1

        return null

结果是：

【Leetcode】142.环形链表II,Leetcode,leetcode,链表,算法

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

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        fast,slow = head,head
        # 现在里边转圈，转到相遇的位置
        while True:
            if not (fast and fast.next): return
            fast,slow = fast.next.next, slow.next
            if fast == slow: break
        
        # 再一步一步到相交的位置
        fast = head
        while fast != slow:
            fast,slow = fast.next,slow.next

        return fast

这种思路太难想了

看了代码随想录的视频

【Leetcode】142.环形链表II,Leetcode,leetcode,链表,算法