Scribd
Upload
46 views1 page

Leetcode 142 Linked List

The document contains a Python implementation of a solution to detect a cycle in a singly-linked list using the Floyd's Tortoise and Hare algorithm. It defines a ListNode class and a Solution class with a method 'detectCycle' that identifies the starting node of the cycle if one exists. If no cycle is detected, the method returns None.

Uploaded by

Weihao Zhang
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
46 views1 page

Leetcode 142 Linked List

The document contains a Python implementation of a solution to detect a cycle in a singly-linked list using the Floyd's Tortoise and Hare algorithm. It defines a ListNode class and a Solution class with a method 'detectCycle' that identifies the starting node of the cycle if one exists. If no cycle is detected, the method returns None.

Uploaded by

Weihao Zhang
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd

# 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
"""
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 如何理解？
if slow == fast:
p = head
q = slow
while p!=q:
p = p.next
q = q.next
#你也可以 return q
return p

return None

You might also like