# The intersection problem of single linked list with or without ring

2022-01-26 23:24:58

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

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) {
return null;
}
//  Quick pointer
//  Slow pointer
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
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
*/
return null;
}

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

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) {
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;
}

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 ：

https://github.com/monday-pro...