判断两个链表是否相交以及如何找到它们相交的第一个结点

向右看齐 2022-10-01 12:48 128阅读 0赞

//判断两个链表是否相交
        public static boolean isIntersect(Node node1,Node node2){
            if ((null == node1) || (null == node2)){
                return false;
            }
            Node tail1 = node1;
            while (tail1.next != null){
                tail1 = tail1.next;
            }
            Node tail2 = node2;
            while (tail2.next != null){
                tail2 = tail2.next;
            }
            return tail1 == tail2;
        }
        //如果两个链表相交,如何找到它们相交的第一个结点
        public static Node getFirstMeetNode(Node node1,Node node2){
            if((null == node1) || (null == node2)){
                return null;
            }
            int len1 = 1;
            Node tail1 = node1;
            //找到链表A最后一个结点
            while (tail1.next != null){
                tail1 = tail1.next;
                len1++;
            }
            int len2 = 1;
            Node tail2 = node2;
            //找到链表B最后一个结点
            while (tail2.next != null){
                tail2 = tail2.next;
                len2++;
            }
            //判断两链表是否相交，不相交,就没意义
            if (tail1 != tail2){
                return null;
            }
            Node t1 = node1;
            Node t2 = node2;
            //找出较长的链表,让之与较短的链表指向位置到相交点距离相等
            if (len1 > len2){
                int distance = len1 - len2;
                while (distance != 0){
                    t1 = t1.next;
                    distance--;
                }
            }else {
                int distance = len2 - len1;
                while (distance != 0){
                    t2 = t2.next;
                    distance--;
                }
            }
            while (t1 != t2){
                t1 = t1.next;
                t2 = t2.next;
            }
            return t1;
        }
        @Test
        public void testIsIntersect() {
            Node n1 = new Node(1);
            Node n2 = new Node(2);
            Node n3 = new Node(3);
            Node n4 = new Node(4);
            Node n5 = new Node(5);
    
            n1.next = n2;
            n2.next = n3;
            n3.next = n4;
            n4.next = n5;
            //n5.next = n2;  //构造一个带环的链表,去除此句表示不带环
            boolean intersect = LinkedList.isIntersect(n1, n3);
            System.out.println(intersect);
            Node firstMeetNode = LinkedList.getFirstMeetNode(n1, n3);
            System.out.println(firstMeetNode.data);
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw_size_16_color_FFFFFF_t_70]: /images/20220118/4f7d687e8c1d4711b2f0c45d971d7eb0.png