struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)

brute force

A、B链表node一一对比，如果相同则为交点。
时间复杂度O(A.length * B.length)
空间复杂度O(1)

hash

同时遍历A、B链表，将每个node的地址存入一个map中，如果发生冲突，则为交点。
时间复杂度O(A.length + B.length)
空间复杂度O(A.length + B.length)

快慢指针找环交点 (Floyd判圈算法)

首先将单链表B首尾相连，整体变为一个有环的链表，问题转化为找环的入口。
定义a：链表头到达入口点的移动步数
定义x：入口点到达相遇点的移动步数
定义r：环的长度
定义t：相遇点到达入口点的移动步数，即 x+t = r
定义L：链表总长度，即 L = a+r = a+x+t

s = a + x
2s = s + n*r

可得
s = n*r

即
a+x = n*r

可得
a + x = (n-1)r + r
a + x = (n-1)r + L - a
a = (n-1)r + L - a - x = (n-1)r + t

结论：从表头设立一个指针，从相遇点设立一个指针，两个同时移动，必然能够在入口点相遇。实际实现非常简单。
时间复杂度O(A.length + B.length)
空间复杂度O(1)

齐头并进

两种实现：

1. 长度更长的那个链表从头节点先遍历abs(len1-en2)，两个链表指针相对尾部对齐。
2. 维护两个指针pA和pB，初始分别指向A和B。然后让它们分别遍历整个链表，每步一个节点。当pA到达链表末尾时，让它指向B的头节点；当pB到达链表末尾时，重新指向A的头节点。
   容易想到，容易实现，面试最佳答案。
   时间复杂度O(A.length + B.length)
   空间复杂度O(1)