题目地址：
https://oj.leetcode.com/problems/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.
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.
方法：
首先，既然是时间复杂度O(n)，那么就不能一个一个点那样试；
其次，既然空间复杂度要求O(1)，既然就不能用stack或者unordered_map之类的数据结构来找链表交点。
那么，我们需要一个比较酷炫的trick来找交点。
先转化问题：
假设有A、B两条链表相交，请求出交点到A链表头结点的距离。（所谓距离，就是头结点走几次能到）
先看具体求法：
0、计算A链表的长度lenA
1、计算B链表的长度lenB
2、逆转A链表（关键）
3、重新计算B链表的长度newLenB
4、返回result = (newLenB - lenB + lenA - 1) / 2
具体到这道题，还需要把A链表又逆转回来，因为你不能更改链表原来的结构。然后重新读取链表，返回第result个结点就OK了。
那么这具体求法究竟是怎么来的？
自己动手试试就明白了。其实就是算出A链表结点在交点旁边的分布数，画图太麻烦了，如果有时间再补一个，或者谁不理解回复一下我就补
全部代码：
/**
* 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) {
if (headA == NULL || headB == NULL)
return NULL;
int addressA; // fin of A.
int addressB; // fin of B.
int lenA = countLength(headA,&addressA);
int lenB = countLength(headB,&addressB);
if (addressA != addressB) // if has a intersect
return NULL;
ListNode *tmpHeadA = (ListNode *)addressA; // to store headA's tail for reverse.
reverseLink(headA);
int newLenB = countLength(headB,&addressB);
int toNew = findCount(lenA,lenB,newLenB);
reverseLink(tmpHeadA);
return findNthNode(headA,toNew);
} int findCount(int lenA,int lenB,int newLenB)
{
int gap = newLenB - lenB;
return (gap + lenA - ) / ;
} ListNode *findNthNode(ListNode *head,int toN)
{
int count = ;
while (toN != count)
{
head = head->next;
count ++;
}
return head;
} int countLength(ListNode *head,int *fin)
{
int count = ;
while (head)
{
*fin = (int)head;
head = head->next;
count ++;
}
return count;
} void reverseLink(ListNode *head)
{
ListNode *pre = NULL;
ListNode *now = head;
ListNode *nxt = head->next;
while ()
{
now->next = pre;
pre = now;
now = nxt;
if (nxt)
nxt = nxt->next;
else
break;
}
}
};