160. Intersection of Two Linked Lists（剑指Offer-两个链表的第一个公共结点）

题目：

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.

思路1：

若两个链表具有交点：1.链表的长度差=相交前的长度差；2.两个链表的最后一个节点相同

因此，具体步骤如下：

1.先计算出两个链表的长度，并得到它们的长度差。

2.在计算长度的过程中，若发现两个链表的最后一个节点不相等，则证明它们没有交点。

3.相对长的链表头部向前移动和长度差大小一样的节点后，两个链表的头部一起向前移动，最终得到交点。

代码1：

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

思路2：

　　思路1需要分别计算链表的长度，思路2则不需要计算长度。用两个指针扫描两个链表，最终两个指针到达NULL或者到达公共结点。

　　假设链表的长度分别为len1和len2，相交后的公共长度为len。长度短的链表优先完成扫描后再去扫描长度长的链表；长度长的链表完成扫描后，去扫描长度短的链表，当两个指针相遇时，指针1走过的长度为len1+len2-len，指针2走过的长度为len2+len1-len，由此可见指针1和指针2走过了相同的长度。

　　我们分4种情况讨论两个链表相交的情况。

两个链表长度相同且无公共交点，此时返回NULL；
两个链表长度相同且有公共交点，只需要遍历一遍就可以得到公共交点；
两个链表长度不同且无公共交点，两遍扫描后返回NULL；
两个链表长度不同且有公共交点，在第二遍扫描的过程中可以相遇。

代码2：

 1 /*
 2 struct ListNode {
 3     int val;
 4     struct ListNode *next;
 5     ListNode(int x) :
 6             val(x), next(NULL) {
 7     }
 8 };*/
 9 class Solution {
10 public:
11     ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
12         if(pHead1 == NULL || pHead2 == NULL)
13             return NULL;
14         
15         ListNode *p1 = pHead1;
16         ListNode *p2 = pHead2;
17         while(p1 != p2){
18             if(p1 != NULL)
19                 p1 = p1->next;
20             else
21                 p1 = pHead2;
22              
23             if(p2 != NULL)
24                 p2 = p2->next;
25             else
26                 p2 = pHead1;
27         }
28         return p1;
29     }
30 };