On the problem of finding the intersection of cyclic and acyclic single linked lists , It is one of the top two problems in the linked list type problem , Let's listen together .
One 、 Title Description
Given two single linked lists that may or may not have rings , Head node head1 and head2.
Please implement a function , If two linked lists intersect , Please return to the first node of the intersection . If they don't intersect , return null
requirement ： If the sum of the lengths of two lists is N, Time complexity, please reach O(N), Please reach O(1).
Two 、 Ideas
The solution is divided into two big steps ：
（1） Find the loop entry node of the single linked list , Acyclic returns null
（2） According to the ring entry node of the obtained linked list , Then discuss
1、 Find the loop entry node of the single linked list , Acyclic returns null
（1） Traverse this single linked list , If the node traversed at a time is null, Then the single linked list must be acyclic
（2） Otherwise there is a ring
Prepare a quick pointer , A slow pointer . At the beginning of the , Both pointers start at the beginning of the node , The fast pointer goes two nodes at a time , The slow pointer goes one node at a time , Until the two hands meet .
here , Fast pointer and start from the node , One node at a time ; The slow pointer continues down from where it meets , Still go one node at a time , When the two pointers meet again, the node is the ring in node .
2、 According to the ring entry node of the obtained linked list , Then discuss
（1） There are no links in both lists
Traverse one of the linked lists , Record the length of the linked list length1 And the last node end1; Traverse another linked list , Record the length of the linked list length2 And the last node end2.
If end1 and end2 Unequal , Then the two linked lists must not intersect ; otherwise , Calculation length1 and length2 The difference between the a, Long list go first a Nodes , Then two linked lists go down one by one , The first equal node is the first node that intersects .
（2） One has a ring 、 An acyclic
In this case, two linked lists cannot intersect .（ You can try to make up such a structure , Remember a little , It's a single chain table ）
（3） Both lists have rings
There are three situations , Each has a ring but does not intersect ; The entry node is the same ; There are two nodes in the loop .
1） Each has a ring but does not intersect
2） The entry node is the same
3） There are two nodes in the loop
The entry nodes of the two linked lists are equal ： That is, the nodes entering the ring are the same , The solution process is the same as that of two linked lists which are acyclic and intersecting , That is, the following rings can be completely ignored when solving .
The ring nodes of the two linked lists are not equal ： Is the first race or the third race . here , Start with one of the looping nodes , Traverse a circle , If you encounter the second entry node when you return to yourself , Is the third kind , Otherwise, it's the first race .
3、 ... and 、 Refer to code for details
1、 Find the loop entry node of the single linked list
/**
* Find the loop entry node of the single linked list , Acyclic returns null
*
* @author Java And algorithm learning ： Monday
*/
public static Node getLoopNode(Node head) {
if (head == null || head.next == null || head.next.next == null) {
return null;
}
// Quick pointer
Node fast = head.next.next;
// Slow pointer
Node slow = head.next;
while (fast != slow) {
// If a fast pointer goes empty , Then the single linked list must be acyclic
if (fast.next == null || fast.next.next == null) {
return null;
}
fast = fast.next.next;
slow = slow.next;
}
// When the fast and slow hands meet , The fast pointer starts from the node again
fast = head;
while (fast != slow) {
// At this time, it is no longer necessary to judge that it is empty , If you can get here, the single linked list must be ring
// At this point, the fast pointer goes one node at a time
fast = fast.next;
// The slow pointer still goes one node at a time
slow = slow.next;
}
return slow;
}
2、 According to the ring entry node of the obtained linked list , Then discuss
（1） There are no links in both lists
/**
* Now we know that the two linked lists are acyclic , Find their first intersection
*
* @author Java And algorithm learning ： Monday
*/
public static Node noLoop(Node head1, Node head2) {
if (head1 == null || head2 == null) {
return null;
}
Node current1 = head1;
Node current2 = head2;
int n = 0;
// The linked list is traversed once to get the length 、 The last node
while (current1.next != null) {
n++;
current1 = current1.next;
}
// The linked list is traversed twice to get the length difference 、 The last node
while (current2.next != null) {
n--;
current2 = current2.next;
}
// If the last node of two linked lists is not equal , Then it must not intersect
if (current1 != current2) {
return null;
}
// The head node of the long linked list is current1
current1 = n > 0 ? head1 : head2;
// The head node of the short linked list is current2
current2 = current1 == head1 ? head2 : head1;
n = Math.abs(n);
// Long list go first n Nodes
while (n != 0) {
n--;
current1 = current1.next;
}
// Two linked lists go down one by one , The first equal node is the first intersecting node
while (current1 != current2) {
current1 = current1.next;
current2 = current2.next;
}
return current1;
}
（3） Both lists have rings
/**
* Both lists have rings
* There are three situations , Each has a ring but does not intersect ; The entry node is the same ; There are two nodes in the loop
*
* @author Java And algorithm learning ： Monday
*/
public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
Node current1 = null;
Node current2 = null;
if (loop1 == loop2) {
current1 = head1;
current2 = head2;
int n = 0;
// Calculation head1 How many nodes are there in the linked list
while (current1 != loop1) {
n++;
current1 = current1.next;
}
// Calculate the difference between the number of nodes in the two linked lists
while (current2 != loop2) {
n--;
current2 = current2.next;
}
// The head node of the long linked list is current1
current1 = n > 0 ? head1 : head2;
// The head node of the short linked list is current2
current2 = current1 == head1 ? head2 : head1;
n = Math.abs(n);
// Long list go first n Nodes
while (n != 0) {
current1 = current1.next;
n--;
}
// Two linked lists go down one by one , The first equal node is the first intersecting node
while (current1 != current2) {
current1 = current1.next;
current2 = current2.next;
}
return current1;
} else {
// The ring nodes of the two linked lists are not equal , Each has a ring but does not intersect, or there are two nodes entering the ring
current1 = loop1.next;
// Start with one of the looping nodes , Traverse a circle , If you encounter the second entry node when you return to yourself , It is There are two nodes in the loop
while (current1 != loop1) {
if (current1 == loop2) {
// At this time, the two loop nodes are the first intersection node , Just return one of them
return loop1;
}
current1 = current1.next;
}
return null;
}
}
The above is the core detailed reference code , I believe that the main method and test method can be written easily , Of course, I want to refer to all the codes , Also attached here is the code for all of this article Github Address ：
