LeetCode 141——环形链表

栏目: 数据库 · 发布时间: 7年前

内容简介:定义快慢两个指针,慢指针每次前进一步,快指针每次前进两步,若链表有环,则快慢指针一定会相遇。用 unordered_map 充当散列表的功能,每次将链表的节点指针作为键值存入 map,如果检测到当前节点指针已经存在于 map 中则说明链表有环。获取更多精彩,请关注「seniusen」!
LeetCode 141——环形链表

2. 解答

2.1 方法 1

定义快慢两个指针,慢指针每次前进一步,快指针每次前进两步,若链表有环,则快慢指针一定会相遇。

/**
 * 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) {
        
        ListNode *slow = head;
        ListNode *fast = head;
        
        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) return true;
        }
         return false;
    }
};
复制代码

2.2 方法 2

用 unordered_map 充当散列表的功能,每次将链表的节点指针作为键值存入 map,如果检测到当前节点指针已经存在于 map 中则说明链表有环。

class Solution {
public:
    bool hasCycle(ListNode *head) {
        
        unordered_map<ListNode *, char> nodemap; // 散列表功能
        ListNode *temp = head;
        
        while (temp)
        {
            if (nodemap.count(temp) == 1) return true; // 当前节点已存在于 map 中,则说明有环
            nodemap[temp] = '0';
            temp = temp->next;
        }
        return false;
    }
};
复制代码

获取更多精彩,请关注「seniusen」!

LeetCode 141——环形链表

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

疯狂又脆弱  坚定又柔软

疯狂又脆弱 坚定又柔软

朱墨 / 湖南文艺出版社 / 2018-3 / 39.80元

《疯狂又脆弱 坚定又柔软》是朱墨的一部作品集,介绍了作者考研到北京,工作在华谊,以及留学去英国的经历,在这短短几年中她一路升职加薪,25岁升任华谊宣传总监,27岁赚到人生的第一笔100万,30岁却毅然离职去英国留学,在表面的光鲜亮丽之下,她也曾付出过外人所不知道的心血和努力。她的人生告诉我们,每一个身居高位或者肆意潇洒的人,都曾为梦想疯狂地倾尽全力,而那些心怀梦想的人也总是怀揣一颗坚定又柔软的内心......一起来看看 《疯狂又脆弱 坚定又柔软》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

SHA 加密
SHA 加密

SHA 加密工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换