题目：
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：
struct ListNode {
int val;
ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (headA == NULL || headB == NULL) {
return NULL;
}
int i;
int lenA = ;
int lenB = ;
ListNode *tempA = headA;
while (tempA->next != NULL) {
tempA = tempA->next;
lenA++;
}
ListNode *tempB = headB;
while (tempB->next != NULL) {
tempB = tempB->next;
lenB++;
}
if (tempA != tempB) {
return NULL;
}
if (lenA > lenB) {
for (i = ; i < lenA - lenB; i++) {
headA = headA->next;
}
} else if (lenA < lenB) {
for (i = ; i < lenB - lenA; i++) {
headB = headB->next;
}
}
while (headA != headB) {
headA = headA->next;
headB = headB->next;
}
return headA;
}
};思路2：
思路1需要分别计算链表的长度，思路2则不需要计算长度。用两个指针扫描两个链表，最终两个指针到达NULL或者到达公共结点。
假设链表的长度分别为len1和len2，相交后的公共长度为len。长度短的链表优先完成扫描后再去扫描长度长的链表；长度长的链表完成扫描后，去扫描长度短的链表，当两个指针相遇时，指针1走过的长度为len1+len2-len，指针2走过的长度为len2+len1-len，由此可见指针1和指针2走过了相同的长度。
我们分4种情况讨论两个链表相交的情况。
- 两个链表长度相同且无公共交点，此时返回NULL；
- 两个链表长度相同且有公共交点，只需要遍历一遍就可以得到公共交点；
- 两个链表长度不同且无公共交点，两遍扫描后返回NULL；
- 两个链表长度不同且有公共交点，在第二遍扫描的过程中可以相遇。
代码2：
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
if(pHead1 == NULL || pHead2 == NULL)
return NULL; ListNode *p1 = pHead1;
ListNode *p2 = pHead2;
while(p1 != p2){
if(p1 != NULL)
p1 = p1->next;
else
p1 = pHead2; if(p2 != NULL)
p2 = p2->next;
else
p2 = pHead1;
}
return p1;
}
};