LeetCode 之 JavaScript 解答第141题 —— 环形链表 I（Linked Lis

wangjuntytl 发布于2019-08-23 16:49 / 2756人阅读

摘要：小鹿题目算法思路两种解题思路哈希表法遍历链表，没遍历一个节点就要在哈希表中判断是否存在该结点，如果存在，则为环否则，将该结点插入到哈希表中继续遍历。

Time：2019/4/7
Title: Linked List Cycle
Difficulty: Easy

Author:小鹿 题目：Linked List Cycle I

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

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:

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

Example 2:

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

Example 3:

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

Follow up:

Can you solve it using O(1) (i.e. constant) memory?

Slove:

▉ 算法思路：

两种解题思路：

1）哈希表法：遍历链表，没遍历一个节点就要在哈希表中判断是否存在该结点，如果存在，则为环；否则，将该结点插入到哈希表中继续遍历。

2）用两个快慢指针，快指针走两步，慢指针走一步，如果快指针与慢指针重合了，则检测的当前链表为环；如果当前指针或下一指针为 null ，则链表不为环。

▉ 方法一：哈希表

   /**
        * Definition for singly-linked list.
        * function ListNode(val) {
        *     this.val = val;
        *     this.next = null;
        * }
        */
        /**
        * @param {ListNode} head
        * @return {boolean}
        */

        var hasCycle = function(head) {
            let fast = head;
            let map = new Map();
            while(fast !== null){
                if(map.has(fast)){
                    return true;
                }else{
                    map.set(fast);
                    fast = fast.next;
                }
            }
            return false;
        };

▉ 方法二：快慢指针

 var hasCycle = function(head) {
     if(head == null || head.next == null){
         return false;
     }
     let fast = head.next;
     let slow = head;
     while(slow != fast){
         if(fast == null || fast.next == null){
             return false;
          }
         slow = slow.next;
         fast = fast.next.next;
     }
     return true;
 };

▉ 方法二：快慢指针

这部分代码是我自己写的，和上边的快慢指针思路相同，运行结果相同，但是当运行在 leetcode 时，就会提示超出时间限制，仔细对比代码，我们可以发现，在逻辑顺序上还是存在差别的，之所以超出时间限制，是因为代码的运行耗时长。

//超出时间限制
var hasCycle = function(head) {
    if(head == null || head.next == null){
        return false;
    }
    let fast = head.next;
    let slow = head;
    while(fast !== null && fast.next !== null){
        if(slow === fast) return true;
        slow = head.next;
        fast = fast.next.next;
    }
    return false;
};

欢迎一起加入到 LeetCode 开源 Github 仓库，可以向 me 提交您其他语言的代码。在仓库上坚持和小伙伴们一起打卡，共同完善我们的开源小仓库！
Github：https://github.com/luxiangqia...

专线服务 idc机房托管 javascript算法题汇编语言程序设计第二版课后题答案 javascript必问面试题 linked

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/103335.html

LeetCode 之 JavaScript 解答第142题 —— 环形链表 II（Linked Li

摘要：说明不允许修改给定的链表。算法思路题目要求返回单链表中存在循环链表的位置。首先，先判断该单链表是否存在循环链表用两个快慢指针分别指向链表的头部，每次移动两步，每次移动一步，移动的步数是的两倍。 Time：2019/4/8Title: Linked List Cycle IIDifficulty: mediumAuthor:小鹿题目：Linked List Cycle II Giv...

whidy 2019-08-23 16:51 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月汇总（55 题攻略）

摘要：微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目录不...

warmcheng 2019-08-26 10:09 评论0 收藏0
LeetCode 141：环形链表 Linked List Cycle

摘要：给定一个链表，判断链表中是否有环。示例输入输出解释链表中有一个环，其尾部连接到第一个节点。哈希表解决重复问题最容易想到的数据结构就是哈希表，哈希表添加节点时只要发现节点已经存在了，证明就有环形链表。给定一个链表，判断链表中是否有环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。 Giv...

chenjiang3 2019-08-16 18:35 评论0 收藏0