Leetcode 142. Linked List Cycle IIJAVA語言

1

2

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

<code>Note: Do not modify the linked list.</code>

題意：不破壞原連結清單的情況下判斷有沒有環，，，，，，

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

<code>/**</code>

<code> </code><code>* Definition for singly-linked list.</code>

<code> </code><code>* class ListNode {</code>

<code> </code><code>*     int val;</code>

<code> </code><code>*     ListNode next;</code>

<code> </code><code>*     ListNode(int x) {</code>

<code> </code><code>*         val = x;</code>

<code> </code><code>*         next = null;</code>

<code> </code><code>*     }</code>

<code> </code><code>* }</code>

<code> </code><code>*/</code>

<code>public</code> <code>class</code> <code>Solution {</code>

<code>    </code><code>public</code> <code>ListNode detectCycle(ListNode head) {</code>

<code>        </code><code>/////不讓修改原來的結構。本來還想用斷鍊法.</code>

<code>        </code><code>if</code><code>(head==</code><code>null</code> <code>|| head.next==</code><code>null</code> <code>||head.next.next==</code><code>null</code><code>)</code><code>return</code> <code>null</code><code>;</code>

<code>        </code><code>ListNode fast=head.next.next;</code>

<code>        </code><code>ListNode slow=head.next;</code>

<code>        </code><code>///判斷有沒有環。找到相遇點</code>

<code>        </code><code>while</code><code>(fast!=slow){</code>

<code>            </code><code>if</code><code>(fast.next!=</code><code>null</code> <code>&amp;&amp; fast.next.next!=</code><code>null</code><code>){</code>

<code>                </code><code>fast=fast.next.next;</code>

<code>                </code><code>slow=slow.next;</code>

<code>            </code><code>}</code><code>else</code><code>{</code>

<code>                </code><code>return</code> <code>null</code><code>;</code>

<code>            </code><code>}</code>

<code>        </code><code>}</code>

<code>        </code><code>fast=head;</code>

<code>            </code><code>fast=fast.next;</code>

<code>            </code><code>slow=slow.next;</code>

<code>        </code><code>return</code> <code>fast;</code>

<code>    </code><code>}</code>

<code>}</code>

裡面有一段推導

本文轉自 努力的C 51CTO部落格，原文連結:http://blog.51cto.com/fulin0532/1905477