单向链表-获取链表交叉节点

今天学习的算法是获取链表交叉节点。

题目介绍

给定两个链表，若链表没有交叉则输出null，若链表交叉则返回交叉节点。
交叉链表如下图所示：

链表交叉-题目 .png

实现思路

老规矩先看图吧：

链表交叉-解题.png

难点说明

这道题相比来说还是比较简单的，这个解题思路有以下三步：

1、先虚拟的将两个链表分表加到对方尾部，这样长度则一样了，记住只是虚拟出两个长度一样的链表。
2、两个移动指针同时从A和B开始移动，当移动到链表的尾部时，则再从另一个链表的头部开始遍历（相当于分别遍历两个虚拟链表）。
3、从图中可以看出终止条件有两个：
一是没有交叉，那最终两个指针都会遍历到对方的尾部节点然后退出即可。
二是若链表交叉了，那么最终两个指针一定会在交叉节点相遇（遍历长度是一样的，而交叉节点之后都一样），相遇节点既为交叉节点。

实现代码

public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    //只要有一个节点的则不会交叉
    if (null == headA || null == headB) {
        return null;
    }
    if(headA == headB){
        return headA;
    }

    ListNode tempA = headA, tempB = headB;
    ListNode tailA = null,tailB = null;

    while (tempA != tempB) {
        if ((tailB != null && tailA != null) && tempA == tailB) {
        return null;
        }
        if (null == tempA.next) {
        tailA = tempA;
        tempA = headB;
        } else {
        tempA = tempA.next;
        }
        if (null == tempB.next) {
        tailB = tempB;
        tempB = headA;
        } else {
        tempB = tempB.next;
        }
    }

    return tempA;
}