环形链表(力扣简单题)(链表)

环形链表

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

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

如果链表中存在环,则返回 true 。 否则,返回 false 。

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:

输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

输入:head = [1], pos = -1
输出:false
解释:链表中没有环。

提示:

链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。

思路

快慢指针龟兔赛跑算法。「Floyd 判圈算法
定义两个指针,一快一慢。慢指针每次只移动一步,而快指针每次移动两步。初始时,慢指针在位置 head,而快指针在位置 head.next。(否则如果都在head进入不了while循环,即假设head前面还有一个虚拟结点,让乌龟和兔子各走一步两步后开始计时)这样一来,如果在移动的过程中,快指针反过来追上慢指针,就说明该链表为环形链表。否则快指针将到达链表尾部,该链表不为环形链表。
因为快指针比慢指针快一步,所以套圈为n圈(n为环的长度)

源码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == nullptr || head->next == nullptr) {
            return false;
        }
        ListNode*slow=head;
        ListNode*fast=head->next;
        while (slow!=fast){
            if (fast == nullptr || fast->next == nullptr) {
                return false;
            }
            slow=slow->next;
            fast=fast->next->next;
        }
    return true;
    }
};
上一篇:一分钟解决数据结构问题----输出该链表中倒数第k个结点


下一篇:LeetCode刷题笔记 链表 遍历链表