LeetCode #142 Linked List Cycle II

Problem

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note

Do not modify the linked list.

Solution

Method: Two Pointers

Time Complexity:

Space Complexity:

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

class Solution:
    def detectCycle(self, head):
        """
        param head, a ListNode   
        return a list node
        """
        try:
            fast = head.next
            slow = head
            while fast is not slow:
                fast = fast.next.next
                slow = slow.next
        except:
            # if there is an exception, we reach the end and there is no cycle
            return None

        # since fast starts at head.next, we need to move slow one step forward
        slow = slow.next
        while head is not slow:
            head = head.next
            slow = slow.next

        return head

Reference

https://leetcode.com/problems/linked-list-cycle-ii/discuss/44902/Sharing-my-Python-solution