【题目】给定两个可能有环也可能无环的单链表,头节点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) { 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 } }