1
The existence of a circular structure in a singly linked list can be roughly drawn as follows:
You can see that the pointer to node5 should point to NULL, but instead points to node2, causing a loop to appear in the list, similar to the structure of a circular single list. If you go through the list, you’re going to loop forever. So how do we find the entrance to the ring?
- Analysis of the
First two speed in the first node set pointer, pointer quickly every time two mobile nodes, and each move slow pointer a node, then according to the experience of the playground run laps, run slow the pointer to the pointer will be run fast “ring”, we put the ring to the entrance they met two point distance is set to a, hypothesis, before meeting quick pointer already ran n ring, ring circumference of C, The distance between the head node and the ring entrance is L, as shown in the figure:
We calculate the distance traveled by the fast pointer (according to the distance traveled by the fast pointer is 2 times that of the slow pointer), and the following equation can be obtained:
After simplification, we can get:
This simplified equation leads to the following conclusion:
- The distance from the beginning to the entrance of the ring is equal to the distance from the entrance of the ring n times minus the distance from the entrance of the ring to the encounter.
- In other words, if one node is told to run from the beginning and the other node is told to run from the encounter, then the two nodes must meet at the entrance to the ring.
Now that the problem is clear, the following two steps are needed:
- Use the fast and slow pointer to find the node where they meet
- Make one pointer run from the beginning node and the other run from the point where they meet, and return the node where they meet
2 Python code implementation
2.1 Building a single linked list
# nodes
class Node(object) :
def __init__(self, element) :
self.element = element
self.next = None
# singly linked list of leading nodes
class linklist(object) :
def __init__(self) :
self.next = None
Add nodes from the tail
def append(self, element) :
node = Node(element)
if self.next= =None:
self.next = node
else:
cur = self.next
while cur.next! =None:
cur = cur.next
cur.next = node
Print the linked list
def traverse(self) :
alist = []
cur = self.next
whilecur ! =None:
alist.append(cur.element)
cur = cur.next
return alist
Copy the code
2.2 Find the encounter node
The solution is relatively simple to ensure that slow nodes move one unit at a time and fast nodes move two units at a time:
def meet(node) :
slow = node.next # slow pointer
fast = node.next.next Quick # pointer
whileslow ! = fast:Stop the loop when the pointer points to the same node
slow = slow.next
fast = fast.next.next
return slow Return the node of any pointer
Copy the code
2.3 Find the ring entrance
Set two Pointers, one to run from the beginning and one to run from the node where they met (call the above function) :
def is_ring(linklist) :
cur1 = linklist.next # pointer to run from the beginning
cur2 = meet(linklist.next) # the node of the encounter
whilecur1 ! = cur2:The node where the two meet is the ring entrance
cur1 = cur1.next
cur2 = cur2.next
return cur1
Copy the code
2.4 test
Create a linked list, insert some data, and point the end pointer to the third node (10) to construct a ring structure:
Create a list
a = linklist()
# insert data
for i in [2.5.10.98.1.3.56]:
a.append(i)
# construct ring
cur = a.next
while cur.next! =None:
cur = cur.next
cur.next = a.next.next.next
Copy the code
# test
b = is_ring(a)
b.element
> 10
Copy the code
As you can see, the third node is returned as (10), and the problem is solved