求两个链表是否相交并返回相交的点

求两个链表是否相交并返回相交的点，或者返回第一个相交的点

两个链表不相交是完全独立的，如果相交那么其中一部分必然是公共的，最容易的想到的结构是这样的：

这种普通链表如果想要求是否相交：

通过遍历找到两个链表的尾结点，如果这两个尾结点相等，代表这两个链表一定是相交的，因为相交就存在公共的尾结点。

public static NodeLinked findEnd(NodeLinked node){
        while (node.next != null){
            node = node.next;
        }
        return node;
    }

// 找到链表1的尾结点
NodeLinked n1_end = findEnd(链表1);
// 找到链表2的尾结点
NodeLinked n2_end = findEnd(链表2);
if(n1_end == n2_end){
// 代表两个普通链表相交
}

但这只是普通的链表，还有一种带环的链表结构，所以除了普通链表的情况还有带环链表的情况：

 针对带环链表的处理，把环的入口所在节点往后的所有节点全部砍掉，将它退化成相交的两个普通链表就能复用之前的逻辑。

 所以需要先找到环的入口，求一个链表的环的入口：

快指针走两步，慢指针走一步，两个指针相遇代表有环，然后快指针从头部开始和慢指针同时开始走，都只走一步，最终相遇就是入口。

// 如果是一个有环的链表，那么返回环的入口节点
// 如果是一个无环的链表，返回链表的尾结点
public static NodeLinked findEnd(NodeLinked node){
       NodeLinked slow = node,fast = node;
        do{
            if(fast != null && fast.next != null){ // 快指针每次走两步，当快指针遇到NULL的时候意味着走到了结尾没有环,
                // 但是反过来判断：不等于NULL的时候让快指针走，为了快指针走完的的时候不让程序结束，直到慢指针走完
                fast = fast.next.next;
            }
            // 慢指针走完就结束
            if(slow.next == null){
                break;
            }
            slow = slow.next;

        } while (slow != fast); // 当快慢指针相遇，意味着有环
        
        if(slow == fast){
            System.out.println("这是一个带环链表,"+slow.value);
            fast = node; // 找到环的入口
            do {
                fast = fast.next;
                slow = slow.next;
            }while (fast != slow);
        }
    }

// 找到链表1的尾结点或环入口
NodeLinked n1_end = findEnd(链表1);
// 找到链表2的尾结点或环入口
NodeLinked n2_end = findEnd(链表2);
// 尾结点相等或环入口相等
if(n1_end == n2_end){ 
// 代表两个普通链表或带环链表相交
}

这样就解决了上边四种情况，然后还有一种特殊的情况：

 一个环，两个链表在同一个环上不同的位置，那么if(n1_end == n2_end)不相等但是也属于相交，所以让链表1的环入口节点n1_end向前移动，如果能找到链表2的环入口节点则代表也属于相交。

同时如果求两个链表第一个相交的点，先计算链表的长度，让最长的链表把相差的距离走完，再一起移动直到相遇就是第一个相交的点

package com.algorithm.question;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 求两个链表是否相交并返回相交的点，这两个链表有可能有环的存在
 */
public class LinkedListTwoIsXJ {

    static LinkedListTwoIsXJ linkedListTwoIsXJ = null;
    static NodeLinked genera = null;

    static NodeLinked n1_insert = null;
    static NodeLinked n2_insert = null;


    public static void main(String[] args) {
        linkedListTwoIsXJ = new LinkedListTwoIsXJ();
        LinkedListTwoIsXJ.NodeLinked n1 = linkedListTwoIsXJ.new NodeLinked();
        LinkedListTwoIsXJ.NodeLinked n2 = linkedListTwoIsXJ.new NodeLinked();
        //1  两条普通的链表相交-验证
        // initgenera();
//        n1 = init(n1);
//        n2 = init2(n2);

        //2 两条带环的链表相交-验证
//        initgeneraTwo();
//        n1 = init(n1);
//        n2 = init2(n2);

        // 3 特殊环的链表相交-验证
        initgeneraTree();
        n1 = init(n1);
        n2 = init2(n2);

        NodeLinked n1_end = findEndNode(n1);
        NodeLinked n2_end = findEndNode(n2);

        NodeLinked xjNode = null;
        if(n1_end == n2_end){ // 两条链表相交(两条普通链表或者带环链表)
            System.out.println("两条普通链表或者带环链表-相交");
            xjNode = findFirstXJ(n1,n2,n1_end,n2_end);
        }else{
            System.out.println("两条特殊链表相交或者不相交");
            xjNode = findFirstXJCycle(n1,n2,n1_end,n2_end);
        }
        System.out.println(xjNode);
        if(xjNode != null){
            System.out.println(xjNode.value);
        }
    }

    public static NodeLinked findEnd(NodeLinked node){
        while (node.next != null){
            node = node.next;
        }
        return node;
    }


    /**
     * 找到两条链表相交的第一个点，包含两条普通链表相交和带环链表相交，
     * 如果是带环链表，n1_end和n2_end是环的入口，以入口作为链表结尾，等同于两条普通链表处理
     * @param n1
     * @param n2
     * @param n1_end
     * @param n2_end
     * @return
     */
    public static NodeLinked findFirstXJ(NodeLinked n1,NodeLinked n2,NodeLinked n1_end,NodeLinked n2_end){

        NodeLinked temp_n1 = n1;
        NodeLinked temp_n2 = n2;
        Integer size_n1 = 0,size_n2 = 0;
        // 求链表1的总长度
        while (temp_n1 != n1_end){
            size_n1++;
            temp_n1 = temp_n1.next;
        }
        // 求链表2的总长度
        while (temp_n2 != n2_end){
            size_n2++;
            temp_n2 = temp_n2.next;
        }
        // 如果链表1更长，那么往前移动直到相等
        temp_n1 = n1;
        while (size_n1 > size_n2){
            size_n1--;
            temp_n1 = temp_n1.next;
        }
        // 如果链表2更长，那么往前移动直到相等
        temp_n2 = n2;
        while (size_n2 > size_n1){
            size_n2--;
            temp_n2 = temp_n2.next;
        }
        // 长度相等的两个链表，往前移动找到第一个相交的点
        while (temp_n1 != temp_n2){
            temp_n1 = temp_n1.next;
            temp_n2 = temp_n2.next;
        }
        return temp_n1;
    }

    public static NodeLinked findFirstXJCycle(NodeLinked n1,NodeLinked n2,NodeLinked n1_end,NodeLinked n2_end){

        NodeLinked temp = n1_end;
        // 进入这个方法的条件是：两个链表完全不想交 || 两个链表特殊相交于一个环上
        // 如果两个链表完全不想交：
        // -- 那么普通链表需要判断是否到达结尾：temp != null
        // -- 带环的链表判断是否在环内循环，避免死循环： temp != n1_end
        // 如果两个链表相交，从n1_end上往前移动一定能遇到n2_end
        do {
            if(temp == n2_end){
                return n1_end;
            }
            temp = temp.next;
        }while(temp != null && temp != n1_end);
        return null;
    }

    /**
     * 如果链表有环就返回环的入口，如果链表没有环就返回最后一个节点
     * @param node
     * @return
     */
    public static NodeLinked findEndNode(NodeLinked node){
        NodeLinked slow = node,fast = node;
        do{
            if(fast != null && fast.next != null){ // 快指针每次走两步，当快指针遇到NULL的时候意味着走到了结尾没有环,
                // 但是反过来判断：不等于NULL的时候让快指针走，这样为了快指针走完的的时候不让程序结束，直到慢指针走完
                fast = fast.next.next;
            }
            // 慢指针走完就结束
            if(slow.next == null){
                break;
            }
            slow = slow.next;

        } while (slow != fast); // 当快慢指针相遇，意味着有环

        if(slow == fast){
            System.out.println("这是一个带环链表,"+slow.value);
            fast = node; // 找到环的入口
            do {
                fast = fast.next;
                slow = slow.next;
            }while (fast != slow);
        }
        return slow;
    }

    public static NodeLinked findEndNodeForSet(NodeLinked node){
        Set<NodeLinked> set = new HashSet<>();
        NodeLinked pre = node;
        while (node != null){
            if(set.contains(node)){
                return node;
            }
            set.add(node);
            pre = node;
            node = node.next;
        }
        return pre;
    }

    /**
     * 构造链表1的测试数据
     * @param headInit
     * @return
     */
    public static NodeLinked init(NodeLinked headInit){
        LinkedListTwoIsXJ.NodeLinked nodeLinked = linkedListTwoIsXJ.new NodeLinked();
        nodeLinked.value = 4;
        if(n1_insert != null){
            nodeLinked.next = n1_insert;
        }else if(genera != null){
            nodeLinked.next = genera;
        }

        headInit = nodeLinked;

        nodeLinked = linkedListTwoIsXJ.new NodeLinked();
        nodeLinked.value = 3;
        nodeLinked.next = headInit;
        headInit.pre = nodeLinked;
        headInit = nodeLinked;

        nodeLinked = linkedListTwoIsXJ.new NodeLinked();
        nodeLinked.value = 2;
        nodeLinked.next = headInit;
        headInit.pre = nodeLinked;
        headInit = nodeLinked;

        nodeLinked = linkedListTwoIsXJ.new NodeLinked();
        nodeLinked.value = 1;
        nodeLinked.next = headInit;
        headInit.pre = nodeLinked;
        headInit = nodeLinked;

        return headInit;
    }

    /**
     * 构造链表2的测试数据
     * @param headInit
     * @return
     */
    public static NodeLinked init2(NodeLinked headInit){
        LinkedListTwoIsXJ.NodeLinked nodeLinked = linkedListTwoIsXJ.new NodeLinked();
        nodeLinked.value = 4;
        if(n1_insert != null){
            nodeLinked.next = n2_insert;
        }else if(genera != null){
            nodeLinked.next = genera;
        }
        headInit = nodeLinked;

        nodeLinked = linkedListTwoIsXJ.new NodeLinked();
        nodeLinked.value = 2;
        nodeLinked.next = headInit;
        headInit.pre = nodeLinked;
        headInit = nodeLinked;

        nodeLinked = linkedListTwoIsXJ.new NodeLinked();
        nodeLinked.value = 3;
        nodeLinked.next = headInit;
        headInit.pre = nodeLinked;
        headInit = nodeLinked;

        nodeLinked = linkedListTwoIsXJ.new NodeLinked();
        nodeLinked.value = 5;
        nodeLinked.next = headInit;
        headInit.pre = nodeLinked;
        headInit = nodeLinked;

        return headInit;
    }

    /**
     * 构造一个普通的公共链表
     */
    public static NodeLinked initgenera() {
        LinkedListTwoIsXJ.NodeLinked nodeLinked = linkedListTwoIsXJ.new NodeLinked();
        nodeLinked.value = 14;
        genera = nodeLinked;

        nodeLinked = linkedListTwoIsXJ.new NodeLinked();
        nodeLinked.value = 13;
        nodeLinked.next = genera;
        genera.pre = nodeLinked;
        genera = nodeLinked;

        nodeLinked = linkedListTwoIsXJ.new NodeLinked();
        nodeLinked.value = 7;
        nodeLinked.next = genera;
        genera.pre = nodeLinked;
        genera = nodeLinked;

        nodeLinked = linkedListTwoIsXJ.new NodeLinked();
        nodeLinked.value = 8;
        nodeLinked.next = genera;
        genera.pre = nodeLinked;
        genera = nodeLinked;

        return genera;
    }

    /**
     * 构造一个带环的公共链表
     * @return
     */
    public static NodeLinked initgeneraTwo() {
        LinkedListTwoIsXJ.NodeLinked nodeLinked = linkedListTwoIsXJ.new NodeLinked();

        LinkedListTwoIsXJ.NodeLinked end = linkedListTwoIsXJ.new NodeLinked();
        end.value = 14;
        genera = end;

        nodeLinked = linkedListTwoIsXJ.new NodeLinked();
        nodeLinked.value = 13;
        nodeLinked.next = genera;
        genera.pre = nodeLinked;
        genera = nodeLinked;

        nodeLinked = linkedListTwoIsXJ.new NodeLinked();
        nodeLinked.value = 7;
        nodeLinked.next = genera;
        genera.pre = nodeLinked;
        genera = nodeLinked;
        end.next = nodeLinked; // 加上环 14->7

        nodeLinked = linkedListTwoIsXJ.new NodeLinked();
        nodeLinked.value = 8;
        nodeLinked.next = genera;
        genera.pre = nodeLinked;
        genera = nodeLinked;

        return genera;
    }

    /**
     * 构造一个圆环的链表
     * @return
     */
    public static NodeLinked initgeneraTree() {
        LinkedListTwoIsXJ.NodeLinked nodeLinked = linkedListTwoIsXJ.new NodeLinked();

        LinkedListTwoIsXJ.NodeLinked end = linkedListTwoIsXJ.new NodeLinked();
        end.value = 14;
        genera = end;

        nodeLinked = linkedListTwoIsXJ.new NodeLinked();
        nodeLinked.value = 13;
        nodeLinked.next = genera;
        genera.pre = nodeLinked;
        genera = nodeLinked;
        n1_insert = nodeLinked; // 链表1的插入点

        nodeLinked = linkedListTwoIsXJ.new NodeLinked();
        nodeLinked.value = 7;
        nodeLinked.next = genera;
        genera.pre = nodeLinked;
        genera = nodeLinked;
        n2_insert = nodeLinked; // 链表2的插入点

        nodeLinked = linkedListTwoIsXJ.new NodeLinked();
        nodeLinked.value = 8;
        nodeLinked.next = genera;
        genera.pre = nodeLinked;
        genera = nodeLinked;
        end.next = nodeLinked; // 加上环 14->8

        return genera;
    }
    class NodeLinked{
        LinkedListTwoIsXJ.NodeLinked next;
        LinkedListTwoIsXJ.NodeLinked pre;
        Integer value;
    }
}