[LeetCode160]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:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

If the two linked lists have no intersection at all, return null.
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.

思路：求一个单链表交集的首结点

　　方法一：找出两个链表的长度差n，长链表先走n步，然后同时移动，判断有没有相同结点

　　方法二：两个链表同时移动，链表到尾部后，跳到链表头部，相遇点即为所求

代码：

方法一：

 1 /**
 2 * Definition for singly-linked list.
 3 * struct ListNode {
 4 *     int val;
 5 *     ListNode *next;
 6 *     ListNode(int x) : val(x), next(NULL) {}
 7 * };
 8 */
 9 class Solution {
10 public:
11     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
12         //方法一
13         ListNode *p = headA; 
14         ListNode *q = headB;
15         if(!p || !q) return NULL;
16         while(p && q && p != q)
17         {
18         p = p->next;
19         q = q->next;
20         if(p == q)
21         return p;
22         if(!p)
23         p = headB;
24         if(!q)
25         q = headA;
26         }
27         return p;
28     }
29 };

方法二：

 1 /**
 2 * Definition for singly-linked list.
 3 * struct ListNode {
 4 *     int val;
 5 *     ListNode *next;
 6 *     ListNode(int x) : val(x), next(NULL) {}
 7 * };
 8 */
 9 class Solution {
10 public:
11     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
12         //方法二
13         if (headA == NULL || headB == NULL) return NULL;
14         ListNode *p = headA;
15         ListNode *q = headB;
16         int countA = 1, countB = 1;
17         while (p->next)
18         {
19             p = p->next;
20             ++countA;
21         }
22         while (q->next)
23         {
24             q = q->next;
25             ++countB;
26         }
27         if (p != q) return NULL;
28         if (countA > countB)
29         {
30             for (int i = 0; i < countA - countB; ++i)
31                 headA = headA->next;
32         }
33         else if (countB > countA)
34         {
35             for (int i = 0; i < countB - countA; ++i)
36                 headB = headB->next;
37         }
38         while (headA != headB)
39         {
40             headA = headA->next;
41             headB = headB->next;
42         }
43         return headA;
44 
45     }
46 };