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 +
'}';
}
}