随笔记录

算法-链表-找两个单项链表首个相交节点

2022-4-9 diaba 算法

package com.jiucaiyuan.net.algrithm.linked;

import java.util.HashSet;
import java.util.Set;

/**
 * <pre>
 * 【问题】找到两个单项链表第一个相交节点
 * 【解题思路】
 * case1：两个无环链表相交
 *      把长链表长出来部分先走完，然后两个链表一起走，如果发现两个链表当前节点相同，则该节点即是所找
 * case2：两个有环链表相交
 *      入环节点是否相同
 *          相同：按照两个无环链表的查找思路，以入环节点为终点查找
 *          不相同：从一个链表的入环节点下一个节点开始向前找，查看是否和第二个链表的入环节点一致，
 *          如果找一圈仍然不一致，不相交，如果找到相同的，返回两个链表的入环节点都可以
 * case3：一个有环，一个无环，不相交
 * 所以主函数得先找两个链表入环节点（判断是否有环）
 * 时间复杂度O(N+M) 空间复杂度O(1)
 * </pre>
 *
 * @Author jiucaiyuan  2022/4/9 19:51
 * @mail services@jiucaiyuan.net
 */

public class FindFirstIntersectNode {

    public static Node getFirstIntersectNode(Node head1, Node head2) {
        if (head1 == null || head2 == null) {
            return null;
        }
        //根据是否有环走不通分支
        Node loop1 = getLoopNode(head1);
        Node loop2 = getLoopNode(head2);
        //如果两个都无环
        if (loop1 == null && loop2 == null) {
            return noLoop(head1, head2);
        }
        //如果两个都有环
        if (loop1 != null && loop2 != null) {
            return bootLoop(head1, head2, loop1, loop2);
        }
        //如果一个有环，一个无环，不相交
        return null;
    }

    /**
     * 两个有环链表，返回第一个相交的节点，如果不相交，返回null
     *
     * @param head1
     * @param head2
     * @param loop1
     * @param loop2
     * @return
     */
    public static Node bootLoop(Node head1, Node head2, Node loop1, Node loop2) {
        Node curr1 = head1;
        Node curr2 = head2;
        //如果入环节点相同，则和无环的两个单链表找相交节点类似：只是终止节点是入环节点，非两个无环节点时以null为终止
        if (loop1 == loop2) {
            //用来记录链表1长度和链表2长度的差
            int n = 0;
            while (curr1.next != loop1) {
                n++;
                curr1 = curr1.next;
            }
            while (curr2.next != loop2) {
                n--;
                curr2 = curr2.next;
            }
            //如果尾结点不同，肯定不相交
            if (curr1 != curr2) {
                return null;
            }
            //curr1指向长链表头
            curr1 = n > 0 ? head1 : head2;
            //curr2指向短链表
            curr2 = n > 0 ? head2 : head1;
            //长链表把长出来部分先走了
            n = Math.abs(n);
            while (n != 0) {
                n--;
                curr1 = curr1.next;
            }
            //两者再一起走，会同时到相交的节点
            while (curr1 != curr2) {
                curr1 = curr1.next;
                curr2 = curr2.next;
            }
            return curr1;
        } else {
            //从loop1.next开始往后找，是否在loop1之前找到loop2，找到就是相交节点，找不到不相交
            curr1 = loop1.next;
            while (curr1 != loop1) {
                if (curr1 == loop2) {
                    return loop1; //返回loop1和loop2都可以
                }
                curr1 = curr1.next;
            }
            return null;
        }
    }

    /**
     * 找单项链表的入环节点，如果有环，返回入环节点，无环返回null
     *
     * @param head
     * @return
     */
    public static Node getLoopNode(Node head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        Node n1 = head.next;
        Node n2 = head.next.next;
        while (n1 != n2) {
            if (n2.next == null || n2.next.next == null) {
                return null;
            }
            n1 = n1.next;
            n2 = n2.next.next;
        }
        n2 = head;
        while (n1 != n2) {
            n1 = n1.next;
            n2 = n2.next;
        }
        return n1;
    }

    /**
     * 返回两个单链表相交的节点（无环场景），如果不相交，返回null
     * 时间复杂度O(N+M)  空间复杂度 O(1)
     *
     * @param head1
     * @param head2
     * @return
     */
    public static Node noLoop(Node head1, Node head2) {
        if (head1 == null || head2 == null) {
            return null;
        }
        Node curr1 = head1;
        Node curr2 = head2;
        //用来记录链表1长度和链表2长度的差
        int n = 0;
        while (curr1.next != null) {
            n++;
            curr1 = curr1.next;
        }
        while (curr2.next != null) {
            n--;
            curr2 = curr2.next;
        }

        //如果尾结点不同，肯定不相交
        if (curr1 != curr2) {
            return null;
        }

        //curr1指向长链表头
        curr1 = n > 0 ? head1 : head2;
        //curr2指向短链表
        curr2 = n > 0 ? head2 : head1;
        //长链表把长出来部分先走了
        n = Math.abs(n);
        while (n != 0) {
            n--;
            curr1 = curr1.next;
        }
        //两者再一起走，会同时到相交的节点
        while (curr1 != curr2) {
            curr1 = curr1.next;
            curr2 = curr2.next;
        }
        return curr1;
    }

    private static void print(Node startNode) {
        Set<Node> hasPrintNodes = new HashSet<>();
        while (startNode != null) {
            if (hasPrintNodes.contains(startNode)) {
                System.out.print("\t[" + startNode.value + "]");
                break;
            }
            hasPrintNodes.add(startNode);
            System.out.print("\t" + startNode.value);
            startNode = startNode.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        Node node8 = new Node(8);
        Node node9 = new Node(9);
        Node node10 = new Node(10);
        Node node11 = new Node(11);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;

        node7.next = node8;
        node8.next = node9;
        node9.next = node10;
        node10.next = node11;

        print(node1);
        print(node7);
        System.out.println("----无环，不相交----------");
        System.out.println("相交节点是=" + getFirstIntersectNode(node1, node7));
        System.out.println("--------------");
        node6.next = node7;
        Node nodejia = new Node(-1);
        Node nodeyi = new Node(-2);
        Node nodebing = new Node(-3);
        nodejia.next = nodeyi;
        nodeyi.next = nodebing;
        nodebing.next = node7;
        print(node1);
        print(nodejia);
        System.out.println("----无环，相交----------");
        System.out.println("相交节点是=" + getFirstIntersectNode(node1, node7));
        node11.next = node6;
        nodejia.next = nodeyi;
        nodeyi.next = nodebing;
        nodebing.next = null;
        print(node1);
        print(nodejia);
        System.out.println("----一个有环，一个无环，不相交----------");
        System.out.println("相交节点是=" + getFirstIntersectNode(node1, nodejia));
        nodebing.next = node7;
        print(node1);
        print(nodejia);
        System.out.println("----两个环，相交----------");
        System.out.println("相交节点是=" + getFirstIntersectNode(node1, nodejia));
        Node nodeding = new Node(-4);
        nodebing.next = nodeding;
        nodeding.next = nodeyi;
        print(node1);
        print(nodejia);
        System.out.println("----两个环，不相交----------");
        System.out.println("相交节点是=" + getFirstIntersectNode(node1, nodejia));
    }

}


class Node {
    int value;
    Node next;
    Node random;

    public Node(int value) {
        this.value = value;
        this.random = null;
        this.next = null;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + value +
                '}';
    }
}