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

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

上一篇:DAY8:Faster-R-CNN简单理解


下一篇:Faster RCNN之进化史