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