题目：
?
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.
解答：
需要的是常量级别的空间，而且时间是遍历的时间（可以常数次的多次遍历）。
因为是单链表，所以没办法从尾部开始回搜到第一个不相同的节点。那能不能从头部开始搜到第一个相同的节点？
好像不行，因为链表的长度各不相同。如果是长度相同的链表就可以了。我们截掉更长的链表的头几个多余元素。
如果我可以知道两者的链表长度，长度通过遍历链表得到。
?
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* ha = headA;
ListNode* hb = headB;
int lenA = 0;
int lenB = 0;
while(ha != NULL) {ha = ha->next; lenA++;}
while(hb != NULL) {hb = hb->next; lenB++;}
ha = headA;
hb = headB;
if(lenA > lenB) {
int diff = lenA - lenB;
while(diff--) ha = ha->next;
}
if(lenB > lenA) {
int diff = lenB - lenA;
while(diff--) hb = hb->next;
}
while(ha) {
if(ha == hb) return ha;
ha = ha->next;
hb = hb->next;
}
return NULL;
}
};
?
?