题目：
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 };
转载于:https://www.cnblogs.com/sindy/p/6829390.html
