本文是在学习中的总结，欢迎转载但请注明出处：http://blog.csdn.net/pistolove/article/details/41593747
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.
思路：
（1）这道算法题是一道较老的题目。记得在数据结构书的习题中出现过。题目不难，但有几个点需要注意。
（2）需要注意：A：链表为空的判断；B：链表是否带有环的判断；C：两链表长度之差处的起始点的寻找。
（3）首先，对链表为空的判断，为空则返回null；
（4）其次，需设置两个临时变量A和B分别指向两链表的起始位置，分别遍历两链表并求得其长度，如果遍历完成A和B指向的不
是同一节点，则说明链表带有环，返回null；
（5）再次，比较两链表的大小，将较大的链表从其起始位置向后移动到两链表长度之差的位置，这样，两链表就出于同一起始位
置了；
（5）最后，判断起始位置对应节点是否相同，不相同则两节点分别后移，最后返回A或B即为结果。
算法代码实现如下所示（PS：题目要求时间复杂度为O(n)，空间复杂度为O(1)，大家有更好的算法希望能分享，谢谢）：
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int lenA = 0;
int lenB = 0;
ListNode A = headA;
ListNode B = headB;
if (A == null || B == null)
return null;
while (A.next != null) {
lenA++;
A = A.next;
}
while (B.next != null) {
lenB++;
B = B.next;
}
// 如果有环状的，终点会不一样，返回null
if (A != B) return null;
A = headA;
B = headB;
// 找到相差的个数，并移动到相同的地方开始比较
if (lenA > lenB) {
for (int i = 0; i < lenA - lenB; i++) {
A = A.next;
}
} else {
for (int i = 0; i < lenB - lenA; i++) {
B = B.next;
}
}
// 如果不相等则比较其后续是否相等
while (A != B) {
A = A.next;
B = B.next;
}
return A;
}