Title: Linked List Cycle II Source: leetcode.com
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.
Follow up:
Can you solve it without using extra space?
Python solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
''' https://leetcode.com/problems/linked-list-cycle-ii/ ''' # 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 """ if not head: return None temp = head temp2 = head hasCycle = False while temp and temp2 and temp2.next: temp = temp.next temp2 = temp2.next.next if temp == temp2: hasCycle = True break if hasCycle: temp = head while temp != temp2: temp = temp.next temp2 = temp2.next else: return None return temp |