leetcode 【 Linked List Cycle II 】 python 实现

浏览数：52 / 时间：2015年06月08日

公司和学校事情比较多，隔了好几天没刷题，今天继续刷起来。

题目：

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

Follow up:
Can you solve it without using extra space?

代码：oj 测试通过 Runtime: 596 ms

 1 # Definition for singly-linked list.
 2 # class ListNode:
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.next = None
 6 
 7 class Solution:
 8     # @param head, a ListNode
 9     # @return a list node
10     def detectCycle(self, head):
11         if head is None or head.next is None:
12             return None
13 
14         dummyhead = ListNode(0)
15         dummyhead.next = head
16         
17         p1 = ListNode(0)
18         p1.next = head
19         p2 = ListNode(0)
20         p2.next = head
21         
22         
23         first_meet = None
24         while p1 is not None and p2 is not None:
25             if p1 == p2:
26                 first_meet = p1
27                 break
28             else:
29                 p1 = p1.next
30                 p2 = p2.next
31                 if p2 is not None:
32                     p2 = p2.next
33         
34         result = None
35         if first_meet is None:
36             return None
37         else:
38             p2 = dummyhead
39             while p1 is not None and p2 is not None:
40                 if p1.next == p2.next:
41                     result = p1.next
42                     break
43                 else:
44                     p1 = p1.next
45                     p2 = p2.next
46         return result
47