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:

1. 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.
2. 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:

1. Use the fast and slow pointer to find the node where they meet
2. 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