142. Linked List Cycle II

题目描述和难度

  • 题目描述:

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

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

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

思路分析

求解关键:

参考解答

参考解答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