找出两个链表的第一个公共节点( 二 ) _公共节点

双指针解决
我们还可以使用两个指针，最开始的时候一个指向链表A ，一个指向链表B ，然后他们每次都要往后移动一位，顺便查看节点是否相等。如果链表A和链表B不相交，基本上没啥可说的，我们这里假设链表A和链表B相交。那么就会有两种情况，

一种是链表A的长度和链表B的长度相等，他们每次都走一步，最终在相交点肯定会相遇。
一种是链表A的长度和链表B的长度不相等，如下图所示

文章插图

虽然他们有交点，但他们的长度不一样，所以他们完美的错开了，即使把链表都走完了也找不到相交点。

我们仔细看下上面的图，如果A指针把链表A走完了，然后再从链表B开始走到相遇点就相当于把这两个链表的所有节点都走了一遍，同理如果B指针把链表B走完了，然后再从链表A开始一直走到相遇点也相当于把这两个链表的所有节点都走完了

所以如果A指针走到链表末尾，下一步就让他从链表B开始。同理如果B指针走到链表末尾，下一步就让他从链表A开始。只要这两个链表相交最终肯定会在相交点相遇，如果不相交，最终他们都会同时走到两个链表的末尾，我们来画个图看一下

文章插图

文章插图

如上图所示， A指针和B指针如果一直走下去，那么他们最终会在相交点相遇，最后再来看下代码

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {//tempA和tempB我们可以认为是A,B两个指针ListNode tempA = headA;ListNode tempB = headB;while (tempA != tempB) {//如果指针tempA不为空 ， tempA就往后移一步 。//如果指针tempA为空 ， 就让指针tempA指向headB（注意这里是headB不是tempB）tempA = tempA == null ? headB : tempA.next;//指针tempB同上tempB = tempB == null ? headA : tempB.next;}//tempA要么是空 ， 要么是两链表的交点return tempA;}

注意：这里所说的指针并不是C语言中的指针，在这里其实他就是一个变量，千万不要搞混了。

问题分析
第一种解法应该是都容易想到的，但效率不高，一个个存储，然后再拿另一个链表的节点一个个判断。最后一种解法没有统计链表的长度，而是当一个链表访问完如果没有找到相交点，就从下一个链表继续访问，一般不太容易想到，也算是比较经典的。