求两条链表的交点

72 阅读 0 评论 48 点赞

我是靠谱客的博主糟糕樱桃，最近开发中收集的这篇文章主要介绍求两条链表的交点，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

求两个相交链表的交点

//求两个相交链表的交点

//①、首先先判断链表是否有环---用快慢指针----当快指针能走到null，则可说明链表为单链表无环--反之则有环
//②、无环相交：
            //先走完两条链表---尾节点地址不一样一定不相交
            //先让长链表 走 与短链表的差值
            // 然后再让两个链表走一样的速度---每次一节点
//③、有环相交
        //1、两个环的第一次入环节点一样---所以交点必然在环的前面---所以可以当初无环链表求交点
        //2、两个环的第一次入环节点不是一样的---先让一个指针沿着环走
            // ---假如遇到了第二个入环节点---则两个链表相交且---loop1和loop2都是入环节点
    
public class IntersectingIinkedList {

    //判断有无环
    public static Node getLinkedListLoop(Node head){
        if (head == null || head.next == null || head.next.next == null){
            return null;
        }
        Node cur1 = head.next;      //慢指针----一次走一个节点
        Node cur2 = head.next.next;  //快指针---一次走两个节点
        //判断是否相遇
        while (cur1 !=cur2){
            if (cur1.next == null || cur2.next.next == null){
                return null;
            }
            cur1 = cur1.next;
            cur2 = cur2.next.next;
        }
        //相遇后快指针返回节点头---并两个都以一个节点为单位移动
        cur2 = head;
        while (cur1 !=cur2){
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        //循环结束说明找到了第一个入环节点---返回节点---快慢指针都可
        return cur1;
    }


    //无环链表相交
    public static Node getIntersecting(Node head1,Node head2){
        int num = 0;   //计算差值
        if (head1 == null || head2 == null){
            return null;
        }
        Node cur1 = head1;
        Node cur2 = head2;
        while (cur1.next != null){
            num++;
            cur1 = cur1.next;
        }
        while (cur2.next !=null){
            num--;   //此时循环结束的n为差值
            cur2 = cur2.next;
        }
        //num的值可能为负或正
        cur1 = num > 0 ? head1 : head2;    //cur1存放长的链表
        cur2 = cur1 == head1 ? head2 : head1;  //cur2存短链表
        num = Math.abs(num);
        //得到差值后让长链表先走
        while (num != 0){
            num--;
            cur1 = cur1.next;
        }
        //然后再两条链表一起走---相遇退出循环
        while (cur1 != cur2){
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }

    //有环链表相交
    public static Node getLoopIntersecting(Node head1,Node loop1,Node head2,Node loop2){
        if (head1 == null || head2 == null){
            return null;
        }

        if (loop1 == loop2){  //相当于单链表相交---因为交点一定是在环之前的
            return getIntersecting(head1,head2);
        }else {
           Node cur1 = loop1.next;
           while (cur1 != loop1){  //回到loop1退出循环---如遇到则相交且两个交点
               if (cur1 == loop2){
                   return loop1;
               }
               cur1 = cur1.next;
           }
        }
        return null;
    }

    //找到两条链表的交点
    public static Node intersectingNode(Node head1,Node head2) {
        if (head1 == null || head2 == null){
            return null;
        }
        Node loop1 = getLinkedListLoop(head1); //获取第一个入环点
        Node loop2 = getLinkedListLoop(head2);
        //获取入环节点，并判断
        if (loop1 == null && loop2 == null){  //无环相交
            return getIntersecting(head1, head2);
        } 
        if (loop1 != null && loop2 != null){  //有环相交
            return getLoopIntersecting(head1,loop1,head2,loop2);
        }
        return null;
    }
}