LeetCode //C - 141. Linked List Cycle-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode //C - 141. Linked List Cycle。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

141. Linked List Cycle

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

LeetCode //C - 141. Linked List Cycle,LeetCode,leetcode,c语言,算法

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

LeetCode //C - 141. Linked List Cycle,LeetCode,leetcode,c语言,算法

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

LeetCode //C - 141. Linked List Cycle,LeetCode,leetcode,c语言,算法

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Constraints:

The number of the nodes in the list is in the range $0, 10^4]$ .
$10^5 <= Node.val <= 10^5$
pos is -1 or a valid index in the linked-list.

From: LeetCode
Link: 141. Linked List Cycle

Solution:

Ideas：

Fundamental Idea:

Imagine two runners on a circular track, one runner (the hare) is much faster than the other (the tortoise). If they start at the same position and run in the same direction, the faster runner (hare) will eventually lap the slower runner (tortoise). Similarly, in a linked list, if there is a cycle, a faster pointer will eventually meet the slower pointer within the cycle.

Code Explanation:

1. Initialization:

We have two pointers: tortoise (slow-moving) and hare (fast-moving). Both start at the head of the linked list.

2. Movement:

The tortoise moves one step at a time (tortoise = tortoise->next).
The hare moves two steps at a time (hare = hare->next->next).

3. Checking for Cycle:

If there is no cycle in the linked list, the hare (which moves faster) will eventually reach the end of the list and encounter a NULL pointer.
If there is a cycle, the hare will eventually “lap” the tortoise, and they will meet at some point inside the cycle.

4. Loop Termination:文章来源地址https://www.toymoban.com/news/detail-676452.html

The loop continues as long as hare and hare->next are not NULL.
If tortoise and hare pointers meet (tortoise == hare), it indicates the presence of a cycle, and the function returns true.
If the loop ends without the pointers meeting, there is no cycle, and the function returns false.

Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

bool hasCycle(struct ListNode *head) {
    if (!head) return false; // If list is empty
    
    struct ListNode *tortoise = head;  // Slow pointer
    struct ListNode *hare = head;      // Fast pointer

    while (hare != NULL && hare->next != NULL) {
        tortoise = tortoise->next;          // Move slow pointer one step
        hare = hare->next->next;            // Move fast pointer two steps
        
        if (tortoise == hare) return true;  // If they meet, there's a cycle
    }

    return false;  // If loop exits, there's no cycle
}