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

資訊專欄INFORMATION COLUMN

[Leecode] Linked List Cycle 鏈表環(huán)

includecmath / 426人閱讀

摘要：快慢指針?lè)◤?fù)雜度時(shí)間空間思路這是一道非常經(jīng)典的雙指針題。如果快指針和慢指針相遇，則說(shuō)明鏈表有環(huán)。代碼快慢指針?lè)◤?fù)雜度時(shí)間空間思路這題是基于上一題，上一題我們發(fā)現(xiàn)相遇后就返回了，而這里我們還要繼續(xù)找到環(huán)的起始點(diǎn)。

Linked List Cycle I 
Given a linked list, determine if it has a cycle in it.
Follow up: Can you solve it without using extra space?
快慢指針?lè)?/b> 復(fù)雜度

時(shí)間 O(N) 空間 O(1)

思路

這是一道非常經(jīng)典的雙指針題。我們從頭設(shè)置一個(gè)快指針，一個(gè)慢指針。快指針一次走兩步，慢指針一次走一步，如果快指針走到了盡頭，則說(shuō)明鏈表無(wú)環(huán)。如果快指針和慢指針相遇，則說(shuō)明鏈表有環(huán)。為什么相遇就說(shuō)明有環(huán)呢？設(shè)想一個(gè)有環(huán)鏈表，快慢指針最后都會(huì)走到環(huán)上，而這個(gè)環(huán)就像一個(gè)環(huán)形跑道一樣，慢指針在后面，快指針在前面，但實(shí)際上快指針也在追慢指針，希望能超慢指針一圈。他們?cè)谶@個(gè)跑道上，總會(huì)有一天快指針追上了慢指針。我們不用擔(dān)心快指針跳過(guò)了慢指針，因?yàn)樗麄儍傻乃俣炔钍?，所以她們倆在環(huán)上的距離總是每次減1，最后總能減到0。

代碼 
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(fast == slow){
                return true;
            }
        }
        return false;
    }
}

2018/10

func hasCycle(head *ListNode) bool {
    fast := head
    slow := head
    // if fast.Next == nil and fast != slow, there can"t be a cycle
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            return true
        }
    }
    return false
}
Linked List Cycle II 
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.


Follow up: Can you solve it without using extra space?
快慢指針?lè)?/b> 復(fù)雜度

時(shí)間 O(N) 空間 O(1)

思路

這題是基于上一題，上一題我們發(fā)現(xiàn)相遇后就返回true了，而這里我們還要繼續(xù)找到環(huán)的起始點(diǎn)。假設(shè)快慢指針在環(huán)上第k個(gè)節(jié)點(diǎn)相遇，而環(huán)的起點(diǎn)是鏈表第m個(gè)節(jié)點(diǎn)，環(huán)的總長(zhǎng)度是n。此時(shí)慢指針再走n-k步就回到了環(huán)的開(kāi)頭，而此時(shí)快指針已經(jīng)走了m+k步。如果我們這時(shí)候?qū)⒖熘羔樂(lè)呕仄瘘c(diǎn)，并讓它也一次走1步，這樣當(dāng)兩個(gè)節(jié)點(diǎn)再次相遇時(shí)，相遇點(diǎn)就是環(huán)的起點(diǎn)。

代碼 
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                // 找相遇點(diǎn)
                slow = head;
                while(slow != fast){
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }
}

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.specialneedsforspecialkids.com/yun/64487.html

相關(guān)文章

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

    摘要：說(shuō)明不允許修改給定的鏈表。算法思路題目要求返回單鏈表中存在循環(huán)鏈表的位置。首先，先判斷該單鏈表是否存在循環(huán)鏈表用兩個(gè)快慢指針?lè)謩e指向鏈表的頭部，每次移動(dòng)兩步，每次移動(dòng)一步，移動(dòng)的步數(shù)是的兩倍。 Time：2019/4/8Title: Linked List Cycle IIDifficulty: mediumAuthor:小鹿 題目：Linked List Cycle II Giv...

    whidy 評(píng)論0 收藏0

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

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

    hoohack 評(píng)論0 收藏0

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

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

    geekzhou 評(píng)論0 收藏0

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

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

    chenjiang3 評(píng)論0 收藏0

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

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

    ysl_unh 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

includecmath

男|高級(jí)講師

TA的文章

閱讀更多
最新活動(dòng)
閱讀需要支付1元查看
<