142. Linked List Cycle II

题目描述和难度

题目描述：

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

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

进阶：
你是否可以不用额外空间解决此题？

题目难度：中等。
英文网址：142. Linked List Cycle II 。
中文网址：142. 环形链表 II 。

思路分析

求解关键：

参考解答

参考解答1：

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

class Solution(object):
    # If there is no cycle, return null.

    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """

        if head is None:
            return None

        slow = head
        fast = head

        while fast:
            fast = fast.next
            if fast:
                fast = fast.next
                slow = slow.next
            else:
                return None
            if fast == slow:
                break

        # 走到这里有两种情况，都要判断
        if fast:
            # 此时 fast == slow 为 True
            point = head
            while slow != point:
                slow = slow.next
                point = point.next
            return point
        else:
            return None

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0142-linked-list-cycle-ii ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。