国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

LeetCode 141：環(huán)形鏈表 Linked List Cycle

ysl_unh / 3437人閱讀

摘要：給定一個鏈表，判斷鏈表中是否有環(huán)。示例輸入輸出解釋鏈表中有一個環(huán)，其尾部連接到第一個節(jié)點。哈希表解決重復問題最容易想到的數(shù)據(jù)結(jié)構(gòu)就是哈希表，哈希表添加節(jié)點時只要發(fā)現(xiàn)節(jié)點已經(jīng)存在了，證明就有環(huán)形鏈表。

給定一個鏈表，判斷鏈表中是否有環(huán)。

為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該鏈表中沒有環(huán)。

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.

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個環(huán)，其尾部連接到第二個節(jié)點。

示例 2：

輸入：head = [1,2], pos = 0
輸出：true
解釋：鏈表中有一個環(huán)，其尾部連接到第一個節(jié)點。

示例 3：

輸入：head = [1], pos = -1
輸出：false
解釋：鏈表中沒有環(huán)。

進階：

你能用 O(1)（即，常量）內(nèi)存解決此問題嗎？

Follow up:

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

解題思路：

? 從頭節(jié)點向后遍歷整個鏈表只要遍歷到節(jié)點為 null ，就證明不是環(huán)形，而如果遍歷到一個節(jié)點的地址之前存在過就證明有環(huán)。

1、哈希表：

解決重復問題最容易想到的數(shù)據(jù)結(jié)構(gòu)就是哈希表，哈希表添加節(jié)點時只要發(fā)現(xiàn)節(jié)點已經(jīng)存在了，證明就有環(huán)形鏈表。并且哈希表查找和插入復雜度都為O(1)，但是空間復雜度會隨著原鏈表長度而增大:O(n)，總的來說：

時間復雜度：O(n)，雖然哈希表的查找和添加操作的時間復雜度是 O(1) ，但是先需要遍歷鏈表然后插入，遍歷的復雜度是O(n)

空間復雜度：O(n)，最多需要保存鏈表的 n個節(jié)點

2、雙指針：

這道題就如同小學跑步問題，假設有兩個人（雙指針）一個快一個慢，不停地向前跑，如果跑得快的那個最后到終點了（遇到空節(jié)點 null），就證明是直線跑道（沒有環(huán)形鏈表）。

如果是存在環(huán)形跑道（環(huán)形鏈表）：兩個人一起跑步（雙指針）一個快一個慢，那么這兩個人因為速度不同，在環(huán)形跑道里跑得快的那個人一定會追上慢的。即兩個指針相遇了，證明存在環(huán)形鏈表。

空間復雜度為O(1)，即進階要求的常量內(nèi)存。

哈希表解題：

Java：

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) return false;//如果是空鏈表直接返回
        Set nodeSet = new HashSet<>();//構(gòu)造哈希表
        while (head.next != null) {//鏈表下一個不為空
            if (nodeSet.contains(head)) return true;//哈希表包含該節(jié)點則存在環(huán)形鏈表
            nodeSet.add(head);//加入節(jié)點
            head = head.next;//下移一位
        }
        return false;
    }
}

Python：

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head is None:
            return False
        hashSet=set()#構(gòu)造集合
        while(head.next is not None):
            if head in hashSet:#是否已存在
                return True
            hashSet.add(head)
            head=head.next
        return False
雙指針解題：

Java：

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {//快指針及其下一位是否為空
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {//如果相遇，存在環(huán)形鏈表
                return true;
            }
        }
        return false;
    }
}

Python：

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head is None or head.next is None:
            return False
        slow, fast = head, head
        while fast is not None and fast.next is not None:
            slow, fast = slow.next, fast.next.next
            if slow == fast:
                return True
        return False
擴展：

python 中is 與 == 區(qū)別 ：

is 用于判斷兩個變量引用對象（即內(nèi)存地址）是否為同一個， == 用于判斷引用變量的值是否相等。

而Python出于對性能的考慮，不可變對象、同一代碼塊中的對象、值相同的對象，都不會重復創(chuàng)建，而是直接引用已經(jīng)存在的對象。

歡迎關(guān)注公眾號：愛寫bug，一起學習。

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

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/45169.html

相關(guān)文章

  • LeetCode 141：環(huán)形鏈表 Linked List Cycle

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

    chenjiang3 評論0 收藏0

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

    摘要：小鹿題目算法思路兩種解題思路哈希表法遍歷鏈表，沒遍歷一個節(jié)點就要在哈希表中判斷是否存在該結(jié)點，如果存在，則為環(huán)否則，將該結(jié)點插入到哈希表中繼續(xù)遍歷。 Time：2019/4/7Title: Linked List CycleDifficulty: Easy Author:小鹿 題目：Linked List Cycle I Given a linked list, determine ...

    wangjuntytl 評論0 收藏0

  • LeetCode 142：環(huán)形鏈表 II Linked List Cycle II

    摘要：如果鏈表無環(huán)，則返回。說明不允許修改給定的鏈表。示例輸入輸出解釋鏈表中有一個環(huán)，其尾部連接到第一個節(jié)點。兩種方法哈希表哈希表添加節(jié)點時只要發(fā)現(xiàn)節(jié)點已經(jīng)存在了，證明就有環(huán)形鏈表。 給定一個鏈表，返回鏈表開始入環(huán)的第一個節(jié)點。 如果鏈表無環(huán)，則返回 null。 為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該...

    hoohack 評論0 收藏0

  • LeetCode 142：環(huán)形鏈表 II Linked List Cycle II

    摘要：如果鏈表無環(huán)，則返回。說明不允許修改給定的鏈表。示例輸入輸出解釋鏈表中有一個環(huán)，其尾部連接到第一個節(jié)點。兩種方法哈希表哈希表添加節(jié)點時只要發(fā)現(xiàn)節(jié)點已經(jīng)存在了，證明就有環(huán)形鏈表。 給定一個鏈表，返回鏈表開始入環(huán)的第一個節(jié)點。 如果鏈表無環(huán)，則返回 null。 為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該...

    geekzhou 評論0 收藏0

  • 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 評論0 收藏0

發(fā)表評論

0條評論

ysl_unh

男|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<