输入两个链表，找出它们的第一个公共节点。
输出：null
解释：这两个链表不相交，因此返回 null。
如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
这道题刚拿到觉得很简单，可以把数字用数组存下来，然后从后向前找寻公共节点。但是有一项要求程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。很难满足。
使用双指针A，B；当他们同时开始运动，A遍历完headA链表就遍历headB链表，而B遍历完headB链表就遍历A链表。A和B总会相遇要么是空，要么是公共节点。
背后的原理是：假设A链表的长度为a，B链表长度为b，公共部分为c；那么在相遇之前A会走a+b-c步，B会走b+a-c步，他们走的步数是相同的，所以只要他们同时开始运动，A指针按照A链表B链表，B指针按照B链表A链表，就会在节点处相遇！
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！