【题目】给定两个可能有环也可能无环的单链表，头节点head1和head2。请实现一个函数，如果两个链表相交，请返回相交的第一个节点。如果不相交，返回null
【要求】如果两个链表长度之和为N，时间复杂度请达到0（N），额外空间复杂度请达到0（1）。
一、先判断一个单链表是否有环
1、哈希表，往哈希表中添加Node节点，如果有重复的value，说明有环，且是第一个入环节点
2、快慢指针：不实用额外空间 如果有环，快慢指针肯定会相遇
相遇之后让快指针指向head，慢指针原位置，然后快慢指针同时移动，再次相遇时就停在入环的Node节点上
二、再判断两个链表是否相交，相交返回相交的第一个节点，不相交，返回null
1、两个无环单链表如果相交，它们相交的Node节点一直走到null，都共有
(1) 先判断两链表尾部Node是否相等，不相等肯定不相交
(2)如果两链表尾部相同，把两个链表的长度相减，差为n，然后让长链链表先走n步，再让两个链表一起走，相遇的时候就是相交的第一个Node
2、一个链表有环，一个链表无环，此时两个链表不可能相交
3、两个有环单链表，3种情况如下
(1)情况2就相当于无环链表的相交问题(将第一个入环的节点看做是终止位置)
(2)对于情况1和情况3，让loop1继续往下走，在转回到自己之前如果能遇到loop2就是情况3（返回loop1或者loop2），如果没有遇到loop2，就是情况1(返回null)
代码
package Algorithms; /** * @author : zhang * @version : 1.0 * @date : Create in 2021/8/11 * @description : */ public class FindFirstIntersectNode { public static class Node { public int value; public Node next; public Node(int data) { this.value = data; } } //返回两个链表相交的第一个节点 public static Node getIntersectNode(Node head1, Node head2) { if (head1 == null || head2 == null) { return null; } Node loop1 = getLoopNode(head1); //拿head1 的入环节点loop1 Node loop2 = getLoopNode(head2); //拿head2 的入环节点loop2 if (loop1 == null && loop2 == null) { //返回两个无环链表相交的第一个节点 return noLoop(head1, head2); } if (loop1 != null && loop2 != null) { //返回两个有环链表相交的第一个节点 return bothLoop(head1, loop1, head2, loop2); } return null; //一个有环一个无环情况 } //返回链表第一个入环节点，如果无环，就返回null public static Node getLoopNode(Node head) { if (head == null || head.next == null || head.next.next == null) { return null; } //定义快慢指针，都先迈出一步， Node n1 = head.next; // n1 -> slow Node n2 = head.next.next; // n2 -> fast //while循环判断是否有环 while (n1 != n2) { if (n2.next == null || n2.next.next == null) { //如果快指针走到结尾，说明无环 return null; } n2 = n2.next.next; //快指针走2步 n1 = n1.next; //慢指针走1步 } //找第一个入环节点 // 跳出while循环说明有环，然后快指针指向head,快慢指针同时移动，再次相遇时就是第一个入环节点 n2 = head; // n2 -> walk again from head while (n1 != n2) { n1 = n1.next; n2 = n2.next; } return n1; //返回入环节点 } //如果两个链表都无环，返回第一个相交节点，如果不相交，返回null public static Node noLoop(Node head1, Node head2) { if (head1 == null || head2 == null) { return null; } Node cur1 = head1; Node cur2 = head2; int n = 0; //通过n++和n--就能求出两链表长度只差 while (cur1.next != null) { n++; cur1 = cur1.next; } while (cur2.next != null) { n--; cur2 = cur2.next; } if (cur1 != cur2) { //如果两个链表尾部Node不同，两个链表肯定不相交 return null; } // n ：链表1长度减去链表2长度的值 cur1 = n > 0 ? head1 : head2; //谁长，谁的头变为cur1 cur2 = cur1 == head1 ? head2 : head1; //谁短，谁的头变为cur2 n = Math.abs(n); while (n != 0) { //长链表先走差值n步 n--; cur1 = cur1.next; } while (cur1 != cur2) { //再让两链表一起移动，相遇时就是第一个入环的节点 cur1 = cur1.next; cur2 = cur2.next; } return cur1; } //如果两个链表都有环，返回第一个相交节点，如果不相交，返回null public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) { Node cur1 = null; Node cur2 = null; if (loop1 == loop2) { //情况2 cur1 = head1; cur2 = head2; int n = 0; while (cur1 != loop1) { n++; cur1 = cur1.next; } while (cur2 != loop2) { n--; cur2 = cur2.next; } cur1 = n > 0 ? head1 : head2; cur2 = cur1 == head1 ? head2 : head1; n = Math.abs(n); while (n != 0) { n--; cur1 = cur1.next; } while (cur1 != cur2) { cur1 = cur1.next; cur2 = cur2.next; } return cur1; } else { cur1 = loop1.next; while (cur1 != loop1) { if (cur1 == loop2) { //情况3 return loop1; } cur1 = cur1.next; } return null; //情况1 } } public static void main(String[] args) { // 1->2->3->4->5->6->7->null Node head1 = new Node(1); head1.next = new Node(2); head1.next.next = new Node(3); head1.next.next.next = new Node(4); head1.next.next.next.next = new Node(5); head1.next.next.next.next.next = new Node(6); head1.next.next.next.next.next.next = new Node(7); // 0->9->8->6->7->null Node head2 = new Node(0); head2.next = new Node(9); head2.next.next = new Node(8); head2.next.next.next = head1.next.next.next.next.next; // 8->6 System.out.println("两个无环链表相交的第一个节点为："+getIntersectNode(head1, head2).value); //6 // 1->2->3->4->5->6->7->4... head1 = new Node(1); head1.next = new Node(2); head1.next.next = new Node(3); head1.next.next.next = new Node(4); head1.next.next.next.next = new Node(5); head1.next.next.next.next.next = new Node(6); head1.next.next.next.next.next.next = new Node(7); head1.next.next.next.next.next.next = head1.next.next.next; // 7->4 // 0->9->8->2... head2 = new Node(0); head2.next = new Node(9); head2.next.next = new Node(8); head2.next.next.next = head1.next; // 8->2 System.out.println("两个有环链表相交第2中情况："+getIntersectNode(head1, head2).value); //2 // 0->9->8->6->4->5->6.. head2 = new Node(0); head2.next = new Node(9); head2.next.next = new Node(8); head2.next.next.next = head1.next.next.next.next.next; // 8->6 System.out.println("两个有环链表相交第3种情况："+getIntersectNode(head1, head2).value); //4 } }