leetcode hot100 环形链表2

142. 环形链表 II

已解答

中等

相关标签

相关企业

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

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

不允许修改 链表。

# 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

        """

        # seen =set()

        # p=head

        # while p!=None:

        #     if p in seen:

        #         return p

        #     else:

        #         seen.add(p)

        #         p=p.next

        # return None

        """

        如何用空间复杂度1实现

        """

        # 快慢指针可以吗

        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

这里是两种方法，第二种 快慢指针，非常男想到啊，需要列出公式，然后推理得到，在快慢指针相遇之后，在经过环外面的路径的长度的话，会到达相交节点