Preface
In the learning of data structures, linked lists are a very common linear structure, and the circular linked list problem is one of the classics of linked list problems. A circular linked list refers to the tail node of the linked list pointing to a node in the linked list, thus forming a ring. Determining whether there are rings in the linked list is the basis for many algorithm problems and is also a common test point in interviews. Today, we will explore in-depth how to detect circular linked lists through a specific question.
Introduction of topics
Determine if there are loops in the linked list
Given a header node for a linked listhead, determine whether there is a ring in the linked list. If there is a ring in the linked list, returntrue; otherwise returnfalse。
For example:
- enter:
head = [3,2,0,-4]，pos = 1（posIndicates the location where the tail node is connected to the linked list, starting from 0) - Output:
true - Explanation: There is a ring in the linked list, and the tail node is connected to the second node.
This question seems simple, but it involves traversal of linked lists, pointer operations and algorithm design. Next, we will analyze how to solve this problem step by step.
Knowledge point analysis
1. Basic concepts of linked lists
A linked list is a linear data structure consisting of a series of nodes, each node consisting of two parts:
- Data field: Store data.
- Pointer field: Stores a pointer to the next node.
For circular linked list issues, we need to pay special attention to the pointer field because it determines the structure of the linked list.
2. Fast and Slow Pointer Method
The core idea of solving the problem of circular linked lists is to use the fast and slow pointer method. The fast and slow pointer method is a common linked list operation technique, which traverses the linked list by setting two pointers (a fast pointer and a slow pointer). The specific steps are as follows:
- Slow pointer: move one step at a time.
- Fast pointer: move two steps at a time.
If there is a ring in the linked list, the fast pointer and the slow pointer will eventually meet within the ring; if there is no ring in the linked list, the fast pointer will first reach the end of the linked list.
3. Pointer operation
In linked list operations, the use of pointers is crucial. We need to be proficient in how to access and modify linked list nodes through pointers. For example:
- use
node->nextAccess the next node. - use
node = node->nextMove the pointer.
In the circular linked list problem, the correct operation of pointers is the basis for implementing the fast and slow pointer method.
Things to note
1. Empty linked list and single-node linked list
When implementing the algorithm, special attention should be paid to the situation where the linked list is empty or there is only one node. For both cases, there is obviously no ring in the linked list, so you can return it directlyfalse。
if (head == NULL || head->next == NULL) {
return false;
}2. Pointer cross-border issue
In linked list operations, you need to ensure that the pointer does not cross the bounds. Especially when the fast pointer moves two steps each time, it must be checked first.fastandfast->nextWhetherNULL。
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
return true;
}
}3. Time complexity and space complexity
The time complexity of the fast and slow pointer method is O(n), where n is the length of the linked list. This is because the fast pointer traverses the linked list at most twice. The space complexity is O(1), because we only use two pointers and do not require additional storage space.
Expand application
1. Find the entrance to the ring
In addition to judging whether there is a ring in the linked list, we can further find the entrance to the ring. This is an important expansion application of the fast and slow pointer method.
When the fast pointer and the slow pointer meet, we can find the entrance to the ring through the following steps:
- Reset the slow pointer to the head node of the linked list.
- The fast pointer remains at the encounter point.
- Both the fast and the slow pointer move one step at a time until they meet again. The encounter point is the entrance to the ring.
The code implementation is as follows:
struct ListNode *detectCycle(struct ListNode *head) {
if (head == NULL || head->next == NULL) {
return NULL;
}
struct ListNode *slow = head;
struct ListNode *fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
break;
}
}
if (fast == NULL || fast->next == NULL) {
return NULL;
}
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}2. Determine the length of the ring
After finding the entrance to the ring, we can further calculate the length of the ring. The method is to start from the entrance of the ring, use a pointer to traverse the ring until it returns to the entrance again.
The code implementation is as follows:
int cycleLength(struct ListNode *head) {
struct ListNode *entry = detectCycle(head);
if (entry == NULL) {
return 0;
}
struct ListNode *temp = entry;
int length = 0;
do {
temp = temp->next;
length++;
} while (temp != entry);
return length;
}Summarize
Through the above analysis and code implementation, we discuss in detail how to detect the ring-link list and further find the entrance of the ring and the length of the ring. The fast and slow pointer method is a very efficient and elegant algorithm. It can not only solve the problem of ring-linked lists, but also be applied to other linked list-related problems.
I hope this article can help you better understand and master the operation of linked lists and the fast and slow pointer method.
The above is the detailed explanation of how to detect and explain the C-language circular link list. For more information about C-language circular link list, please pay attention to my other related articles!