462. 找出两个链表的第一个公共节点( 二 ) 问题描述输入两个链表

一种是链表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语言中的指针，在这里其实他就是一个变量，千万不要搞混了。
问题分析
第一种解法应该是都容易想到的，但效率不高，一个个存储，然后再拿另一个链表的节点一个个判断。最后一种解法没有统计链表的长度，而是当一个链表访问完如果没有找到相交点，就从下一个链表继续访问，一般不太容易想到，也算是比较经典的。