A fast or slow pointer is a typical use of a double pointer, usually controlling two Pointers to move at different speeds to solve a problem. Using fast and slow Pointers to solve problems is often clever. In this paper, we learn the usage of fast and slow Pointers by analyzing several examples, and analyze its essence, and finally achieve the purpose of convenient memory, flexible use.
Next, let’s look at four examples: determining whether a list has a ring, finding the entrance to the list’s ring, finding the middle node of the list, and finding the NTH node from the bottom of the list.
Check whether the list has rings
Title (source Leetcode)
“Give you the head of a linked list and check if there are rings in the list.
If there is a node in the list that can be reached again by continuously following the next pointer, then there is a ring in the list. To represent the rings in a given list, the metric system internally uses the integer POS to represent where the tail of the list is connected to in the list (the index starts at 0). Note: pos is not passed as an argument. Just to identify the reality of linked lists.
Returns true if there are rings in the list. Otherwise, return false.”
Circular lists: leetcode-cn.com/problems/li…
Analysis of the
There are two common solutions to this problem: 1. Hash table 2. Fast and slow Pointers. We mainly analyze the solution of fast and slow Pointers:
We define two Pointers: a slow moving pointer is called a slow pointer, and a fast moving pointer is called a fast pointer. The slow pointer moves one node at a time in the linked list, and the fast pointer moves two nodes at a time in the linked list. If the two Pointers eventually meet, it means there is a ring. If the fast pointer reaches the end of the list, there is no loop.
Encounter: fast pointer = slow pointer; Reach the end: The next node of the fast pointer is Null.
To understand this solution, you need to understand the Floyd loop detection algorithm.
Floyd loop detection Algorithm is also called Tortoise and Hare Algorithm. The tortoise runs slowly and the hare runs fast. The tortoise and the hare were in a race. If there were a ring, the hare would surely catch up with the tortoise.
We compare the tortoise to the slow pointer and the rabbit to the fast pointer moving simultaneously in the linked list. The difference between running and pointer movement is that the distance of running is continuous, while the fast pointer moves two nodes at a time is discontinuous. On the other hand, if there are rings in the list, then the smallest ring needs two nodes, so if there are rings, the fast pointer can move two nodes at once without missing any rings. And whether the ring has an odd or even number of nodes, the fast pointer will eventually overlap with the slow pointer at some node.
The answer
Based on the above analysis, we give the following code:
Func hasCycle (head * ListNode) bool {if head = = nil | | head. The Next = = nil {/ / if the list have zero or one node, Return false} slowPoint, fastPoint := head, head.Next = slowPoint {/ / if equal speed pointer end loop, proved to have a ring if fastPoint = = nil | | fastPoint. Next = = nil {/ / fast if the pointer to the finish before or at the end of the reciprocal of the first node, SlowPoint = slowPoint.Next fastPoint = fastPoint.next.Next} return true}Copy the codeLook for the entry in the middle of the list
Title (source Leetcode)
“Given the head of a linked list, return the first node at which the list begins to loop. Returns NULL if the list is loopless.
If there is a node in the list that can be reached again by continuously following the next pointer, then there is a ring in the list. To represent the rings in a given list, the metric system internally uses the integer POS to represent where the tail of the list is connected to in the list (the index starts at 0). If pos is -1, there are no rings in the linked list. Note: POS is not passed as an argument, just to identify the actual state of the list.”
Circular linked list II: leetcode-cn.com/problems/li…
Analysis of the
This problem and the previous problem, usually hash table, fast and slow pointer two solutions. We mainly analyze the solution of fast and slow Pointers:
We define two Pointers: a slow moving pointer is called a slow pointer, and a fast moving pointer is called a fast pointer. The slow pointer moves one node at a time in the linked list, and the fast pointer moves two nodes at a time in the linked list. If the two Pointers eventually meet, it means there is a ring. If the fast pointer reaches the end of the list, there is no loop.
In the presence of a ring, we assume that the fast and slow Pointers meet at D. A represents the length before entering the ring, B represents the length after the slow pointer enters the ring and then goes through B, and C represents the remaining length of the ring. The pointer points in the clockwise direction of the circle.
- If the fast pointer and the slow pointer meet at D, then the fast pointer has gone n more times than the slow pointer, which is the length of n times b plus c.
- In this case, the distance traveled by the fast pointer is a+ N *(b+c)+b, and the distance traveled by the slow pointer is a+b.
- Since the fast pointer takes two steps at a time and the slow one at a time, the fast pointer always travels twice as far as the slow pointer, so a+n*(b+c)+b=2(a+b)*
- From the above formula, a is equal to (n-1) times (b+c)+c, which means that the length of a is exactly the length of the n-1 circle plus the distance from D to the encounter point.
According to the above inference, when the fast and slow Pointers meet, we apply another pointer to start from the head of the linked list and move one node at a time, while the slow pointer moves one node at a time. The final meeting point of the two Pointers is the entry point of the ring.
The answer
func detectCycle(head *ListNode) *ListNode { slowPoint, fastPoint := head, head for fastPoint ! = nil && fastPoint.Next ! = nil {// If the fast pointer reaches the end or the last node before the end, there is no loop. SlowPoint = slowPoint.Next fastPoint = fastpoint.next.Next if fastPoint == slowPoint {// If fastPoint == slowPoint; delectPoint := head for delectPoint ! SlowPoint {// If the slowPoint pointer is equal to the delectPoint pointer from the beginning, the current node is the entry point of the loop. delectPoint = delectPoint.Next slowPoint = slowPoint.Next } return delectPoint } } return nil }Copy the codeFind the intermediate node of the linked list
Title (source Leetcode)
Given a non-empty singly linked list with head, return the middle node of the list.
If there are two intermediate nodes, the second intermediate node is returned.
Intermediate nodes of the linked list: leetcode-cn.com/problems/mi…
Analysis of the
There are many ways to solve this problem, but the fast and slow pointer solution is very clever. We define two Pointers: a slow moving pointer is called a slow pointer, and a fast moving pointer is called a fast pointer. Slow Pointers move one node at a time in the linked list, fast Pointers move two nodes at a time in the linked list. Because the fast pointer always moves twice as far as the slow pointer, when the fast pointer moves to the end of the list, the slow pointer is right in the middle of the list.
The answer
func middleNode(head *ListNode) *ListNode { slowPoint, fastPoint := head, head for fastPoint! = nil && fastPoint.Next ! = nil{ slowPoint = slowPoint.Next fastPoint = fastPoint.Next.Next } return slowPoint }Copy the codeFind the NTH node to the end of the list
The title
Given a linked list, find the NTH node to the end of the list and return.
Analysis of the
There are many ways to solve this problem, but the fast and slow pointer solution is very clever. We define two Pointers: two Pointers move one node at a time. We’re going to let one of the Pointers move n nodes first, and we’re going to call the first one fast, and we’re going to call the second one slow. Then both Pointers move at the same time. Because the speed of movement is the same, the distance between the two Pointers is always N, and when the fast pointer reaches the end of the list, the slow pointer points to the NTH node from the bottom of the list.
Here is called “fast and slow pointer” a little far-fetched, feel called before and after the pointer is more appropriate, but for convenient memory for fast and slow pointer.
The answer
func findNthFromEnd(head *ListNode, n int) *ListNode { fastPoint,slowPoint := node,node for i:=0; i<n+1; i++{ fastPoint = fastPoint.Next } for fastPoint ! = nil { fastPoint= fastPoint.Next slowPoint = slowPoint.Next } return slowPoint }Copy the codeconclusion
In this article we introduce the common uses of fast and slow Pointers:
- Using Floyd circle detection algorithm to find loops.
- Use Floyd circle detection algorithm to find the entrance of the ring.
- Find the intermediate node of the linked list.
- Find the NTH node to the end of the list.
In Floyd ring detection algorithm, the problem of judging ring is abstracted into the problem that two Pointers moving around the ring will meet eventually, and the problem is solved through the vivid scene of ring track. When looking for the middle node of the linked list, the speed difference between two Pointers is used to make the distance of one pointer always half of the other pointer, and the speed and distance of the pointer are used to solve the problem. When looking for the NTH node from the bottom of the linked list, the two Pointers with the same speed are always kept n relative distance, which abstracts the linked list problem into the distance problem.
These methods all abstract the algorithm problem into the distance and velocity of two Pointers, and finally reach the conclusion through mathematical formula derivation. By extension, we can use similar methods to abstract problems and derive solutions for linked lists in the future.