LeetCode 之 JavaScript 解答第141題 —— 環(huán)形鏈表 I（Linked Lis

wangjuntytl 發(fā)布于2019-08-23 16:49 / 2846人閱讀

摘要：小鹿題目算法思路兩種解題思路哈希表法遍歷鏈表，沒遍歷一個節(jié)點就要在哈希表中判斷是否存在該結點，如果存在，則為環(huán)否則，將該結點插入到哈希表中繼續(xù)遍歷。

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）哈希表法：遍歷鏈表，沒遍歷一個節(jié)點就要在哈希表中判斷是否存在該結點，如果存在，則為環(huán)；否則，將該結點插入到哈希表中繼續(xù)遍歷。

2）用兩個快慢指針，快指針走兩步，慢指針走一步，如果快指針與慢指針重合了，則檢測的當前鏈表為環(huán)；如果當前指針或下一指針為 null ，則鏈表不為環(huán)。

▉ 方法一：哈希表

   /**
        * 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 時，就會提示超出時間限制，仔細對比代碼，我們可以發(fā)現(xiàn)，在邏輯順序上還是存在差別的，之所以超出時間限制，是因為代碼的運行耗時長。

//超出時間限制
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...

GPU云服務器云服務器 javascript算法題匯編語言程序設計第二版課后題答案 javascript必問面試題 linked

文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/103335.html

LeetCode 之 JavaScript 解答第142題 —— 環(huán)形鏈表 II（Linked Li

摘要：說明不允許修改給定的鏈表。算法思路題目要求返回單鏈表中存在循環(huán)鏈表的位置。首先，先判斷該單鏈表是否存在循環(huán)鏈表用兩個快慢指針分別指向鏈表的頭部，每次移動兩步，每次移動一步，移動的步數(shù)是的兩倍。 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 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經(jīng)到題，所以后面會調整自己，在刷算法與數(shù)據(jù)結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區(qū)別...

tain335 2019-08-26 10:28 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

摘要：微信公眾號記錄截圖記錄截圖目前關于這塊算法與數(shù)據(jù)結構的安排前。已攻略返回目錄目前已攻略篇文章。會根據(jù)題解以及留言內容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協(xié)議授權之外的使用權限可以從處獲得。 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：環(huán)形鏈表 Linked List Cycle

摘要：給定一個鏈表，判斷鏈表中是否有環(huán)。示例輸入輸出解釋鏈表中有一個環(huán)，其尾部連接到第一個節(jié)點。哈希表解決重復問題最容易想到的數(shù)據(jù)結構就是哈希表，哈希表添加節(jié)點時只要發(fā)現(xiàn)節(jié)點已經(jīng)存在了，證明就有環(huán)形鏈表。給定一個鏈表，判斷鏈表中是否有環(huán)。為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果 pos 是 -1，則在該鏈表中沒有環(huán)。 Giv...

chenjiang3 2019-08-16 18:35 評論0 收藏0