Leetcode No.141 Linked List Cycle环形链表(c++实现）

2023-12-22 14:43:34

1. 题目

1.1 英文题目

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

1.2 中文题目

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪next指针再次到达，则链表中存在环。为了表示给定的环，我们使用整数pos来表示链表尾连接到链表中的位置（索引从0开始）。如果pos是-1，则在该链表中没有环。注意：pos不做为参数进行传递，仅仅是为了表示链表的实际情况，pos为-1或者链表中的一个有效索引

如果链表中存在环，则返回true，并返回环入口在链表中的位置、环的周长。否则，返回false。

1.3输入输出

输入	输出
head = [3,2,0,-4], pos = 1	true
head = [1,2], pos = 0	true
head = [1], pos = -1	false

1.4 约束条件

The number of the nodes in the list is in the range [0, 104].
-105 <= Node.val <= 105
pos is -1 or a valid index in the linked-list.

2. 分析

2.1 快慢指针法

代码如下：

class Solution {
 public:
     bool hasCycle(ListNode* head) {
         ListNode* faster = head;//慢指针
         ListNode* slower = head;//快指针
         while (faster != nullptr && faster->next != nullptr) {
             faster = faster->next->next;//快指针一次走两步
             slower = slower->next;//慢指针一次走一步
             if (faster == slower) {//快慢指针相遇，说明存在环
                 return true;
             }
         }
         return false;//不存在环的情形
     }
 };

参考：https://leetcode.com/problems/linked-list-cycle/discuss/44604/My-faster-and-slower-runner-solution

码农公寓