leetCode 160. Intersection of Two Linked Lists 連結清單

160. Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

begin to intersect at node c1.

Notes:

If the two linked lists have no intersection at all, return <code>null</code>.

The linked lists must retain their original structure after the function returns.

You may assume there are no cycles anywhere in the entire linked structure.

Your code should preferably run in O(n) time and use only O(1) memory.

題目大意：

找出兩個連結清單後半部分的交彙點。

思路：

1.求出兩個連結清單的長度。

2.擷取連結清單長度差n。

3.将長的連結清單先移動到第n個節點。

4.對長連結清單和短連結清單進行比較。(同時向後移動)如果在連結清單尾之前找到相等的節點，傳回該節點，如果沒找到，傳回NULL。

代碼如下：

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

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

<code>/**</code>

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

<code> </code><code>* struct ListNode {</code>

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

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

<code> </code><code>*     ListNode(int x) : val(x), next(NULL) {}</code>

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

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

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

<code>public</code><code>:</code>

<code>    </code><code>int</code> <code>listLength(ListNode *head)</code><code>//用快指針求連結清單長度</code>

<code>    </code><code>{</code>

<code>        </code><code>ListNode * p = head;</code>

<code>        </code><code>int</code> <code>i = 0 ;</code>

<code>        </code><code>while</code><code>(p &amp;&amp; p-&gt;next)</code>

<code>        </code><code>{</code>

<code>            </code><code>i++;</code>

<code>            </code><code>p = p-&gt;next-&gt;next;</code>

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

<code>        </code><code>if</code><code>(p == NULL)</code>

<code>            </code><code>return</code> <code>2 * i;</code>

<code>        </code><code>return</code> <code>2 * i + 1;</code>

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

<code>    </code><code>ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {</code>

<code>        </code><code>int</code> <code>lenA = listLength(headA);</code>

<code>        </code><code>int</code> <code>lenB = listLength(headB);</code>

<code>        </code> 

<code>        </code><code>int</code> <code>maxLen = lenA &gt; lenB ? lenA :lenB;</code>

<code>        </code><code>int</code> <code>remain ; </code>

<code>        </code><code>ListNode * la,*lb;</code>

<code>        </code><code>la = headA;</code>

<code>        </code><code>lb = headB;</code>

<code>        </code><code>if</code><code>(maxLen == lenA)</code>

<code>            </code><code>remain = lenA - lenB;</code>

<code>            </code><code>while</code><code>(remain--)</code>

<code>            </code><code>{</code>

<code>                </code><code>la = la-&gt;next;</code>

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

<code>        </code><code>else</code>

<code>            </code><code>remain = lenB - lenA;</code>

<code>                </code><code>lb = lb-&gt;next;</code>

<code>        </code><code>while</code><code>(lb != NULL)</code>

<code>            </code><code>if</code><code>(la != lb)</code>

<code>            </code><code>else</code>

<code>                </code><code>return</code> <code>la;</code>

<code>        </code><code>return</code> <code>NULL;</code>

<code>};</code>

本文轉自313119992 51CTO部落格，原文連結:http://blog.51cto.com/qiaopeng688/1837480