From running on the road to forming a link list: Exploring the detection of circular link list
The ring in life
Imagine two people running on the circular track, one running fast and the other running slowly. If they keep running, the fast runner will definitely catch up with the slow runner from behind. This is the realistic mapping of the circular list problem we are going to discuss today. On the track, if two runners with different speeds meet, it means that the track is ring-shaped; also in the linked list, if two pointers with different speeds meet, it means that there is a ring in the linked list.
Problem description
LeetCode Question 141 "Ring Link List" requirements: Give you a head of the link list to determine whether there is a ring in the link list. If there is a node in the linked list, it can be reached again by continuously tracking the next pointer, then a ring exists in the linked list.
For example:
Enter: 3 → 2 → 0 → -4
↑________________|
Output: true
Explanation: There is a ring in the linked list, and the tail node is connected to the second node
Enter: 1 → 2
↑___|
Output: true
Explanation: There is a ring in the linked list, and the tail node is connected to the first node
Enter: 1 → 2 → 3 → 4
Output: false
Explanation: There is no ring in the linked listSimple solution: hash table record
The most intuitive idea is to use a hash table to record each passing node. It’s like sprinkling bread crumbs on the runway. If you encounter a place where crumbs have been sprinkled, it means that the path forms a ring.
Hash table solution implementation
public boolean hasCycle(ListNode head) {
Set<ListNode> see = new HashSet<>();
while (head != null) {
// If you have seen this node, it means there is a ring
if ((head)) {
return true;
}
// Record the current node
(head);
head = ;
}
return false;
}Optimization solution: Fast and Slow Pointer (Floyd Circle Determination Algorithm)
This classic algorithm is also called the "tortoise and hare racing algorithm", just like the running scenario we started with: let two pointers move on the linked list, if there is a ring, the fast pointer will eventually catch up with the slow pointer.
Why do fast and slow pointers meet?
Imagine on the ring track:
- Fast pointer walks 2 steps each time, slow pointer walks 1 step each time
- Relatively speaking, the fast pointer is catching up with the slow pointer for 1 step each time.
- If there is a ring, it's like catching up on the playground. The fast pointer will definitely catch up with the slow pointer.
- If there is no loop, the fast pointer will first reach the end point
Code implementation and detailed explanation
public boolean hasCycle(ListNode head) {
if (head == null || == null) {
return false;
}
// Initialize the fast and slow pointer
ListNode slow = head;
ListNode fast = head;
// Fast pointer takes two steps each time, slow pointer takes one step each time
while (fast != null && != null) {
slow = ; // Take a step on the slow pointer
fast = ; // Two steps for fast pointer
// If two pointers meet, there is a ring
if (slow == fast) {
return true;
}
}
// If the fast pointer reaches the end of the linked list, it means there is no loop
return false;
}Graphical process
Take a linked list as an example:
1) Initial status:
3 → 2 → 0 → 4
↑____________|
S,F
(S=slow, F=fast)
2) After the first move:
3 → 2 → 0 → 4
↑____________|
S F
3) After the second move:
3 → 2 → 0 → 4
↑____________|
S F
4) The final encounter:
3 → 2 → 0 → 4
↑____________|
S,FComparison of complexity
Hash table solution:
- Time complexity: O(n)
- Space complexity: O(n), need to store accessed nodes
- Advantages: Intuitive thinking, easy to implement
- Disadvantages: Additional space is required
Fast and Slow Pointer Solution:
- Time complexity: O(n)
- Space complexity: O(1), only two pointers are required
- Advantages: High space efficiency and achieve elegance
- Disadvantages: You need to understand the mathematical principles of fast and slow pointers
Core principle analysis
1. Mathematical Proof
Why do fast and slow pointers meet?
- Assume that the ring length is K, and the length before entering the ring is N
- When the slow pointer takes S step, the fast pointer takes 2S steps
- The S step that the fast pointer takes more must be an integer multiple of the ring length K
- Therefore, the fast and slow pointers will definitely meet in the K-N step after entering the ring
2. Critical situation analysis
- Empty link table
- Single node link table
- The length of the ring is 1 (self-ring)
- The entry point at the beginning or end
Summary of practical skills
Key points to solve the ring problem:
- Master fast and slow pointer skills
- Understand the characteristics of ring structures
- Consider boundary situations
- Pay attention to the order in which pointers move
Related ring problems:
- Find the entrance point of the ring
- Calculate the length of the ring
- Find a specific node in the ring
summary
The detection problem of circular linked lists is a classic problem in linked list operations. It teaches us:
- How to solve complex problems with minimal space
- The powerful algorithm technique of fast and slow pointer
- How to map real problems to algorithmic thinking
- Elegant solutions often come from profound mathematical principles
Suggestion: Think more about the application scenarios of fast and slow pointers. It is not only used for detection rings, but also:
- Find the midpoint of the linked list
- Determine whether the linked list is a backdrop
- Find the K-last node
These problems can be solved in a similar way of thinking!
Author: Ninja Algorithm
Official account: Ninja Algorithm
I have prepared a list of questions to practice and detailed questions for these questions, covering most common interview questions. I can say responsibly that as long as you truly master these questions, 80% of the algorithm interviews will encounter similar questions. Reply to the official account [Question List] to obtain ~