Algorithms – Single Link List and Ring
When we encounter a problem, the problem of single linked list and ring, we should sort out all kinds of solutions.
1.1. Is there a ring?
- Listing the unique identifier of the linked list, traversing the linked list to determine whether there is a unique identifier of the current node in the table, which represents a ring, or adding the unique identifier of the current node to the list.
Time complexity is optimal and space complexity is high.
- Fast and slow pointer, fast pointer moving step is 2, slow pointer moving step is 1, if the two meet, then there are rings, if the fast pointer is NULL, that is to say, to the end of the chain, then there are no rings.
1.2. Length of rings
- Chain length – acyclic length, in other words, (list length + 1) – list. index (current node ID)
- When the slow pointer enters the ring, the distance between the fast pointer and the slow pointer is n, so when they meet, they must move n times.
Now the position of the fast and slow pointer coincides, and then moves forward. Moving R times, the two meet again, indicating that the fast pointer catches up with the slow pointer. The length of the pursuit is equal to the length of the ring.
1.3. The Starting Point of a Ring
- list.index(Current node ID)
- Let’s assume that the length from the starting point to the starting point of the ring is LenA; from the beginning to the first encounter, it moves t step; the length of the ring is R; and the distance from the starting point of the ring to the first encounter position of the two rings is X. When the two encounters, the fast pointer has turned n circles on the ring.
The following equation holds: the distance of slow pointer movement = LenA + x; t = LenA + x;
The distance of fast pointer movement = LenA + n * R + x; that is, 2T = LenA + n * R + x;
So 2* (LenA + x) = LenA + n * R + x;
LenA = n * R – x;
The equation above can be understood as follows: if the slow pointer moves from the beginning of the list, the fast pointer moves from the beginning of the ring. When the slow pointer moves from the beginning to the beginning of the ring, the fast pointer always moves on the ring, and it moves N cycles by X steps. Then we can conclude that if the slow pointer starts at the beginning of the list.When the slow pointer reaches the starting point of the ring, the fast pointer also reaches the starting point of the ring, that is, they point to the same node.