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

資訊專欄INFORMATION COLUMN

[LintCode] Linked List Cycle I & II

用戶83 / 3492人閱讀

摘要：做法如果有環(huán)，快慢指針必定可以相遇。而讓此時(shí)重新從起點(diǎn)出發(fā)，以和相同的速度，需要走非環(huán)路的直線長(zhǎng)度，才能到達(dá)環(huán)的起點(diǎn)。也就是說(shuō)，，就是第二個(gè)循環(huán)結(jié)束的條件。

Linked List Cycle I Problem

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

Example

Given -21->10->4->5, tail connects to node index 1, return true

Note

做法：如果有環(huán)，快慢指針必定可以相遇。
注意兩點(diǎn)：初始化快慢指針的時(shí)候，fast要在slow后面，也就是head.next；由于fast一次走兩步，所以while循環(huán)里要判斷兩個(gè)位置是否為null：fast和fast.next。

Solution 
public class Solution {
    public boolean hasCycle(ListNode head) {  
        if (head == null/* ||head.next == null */) return false;
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast != slow) {
            if (fast == null || fast.next == null) return false;
            fast = fast.next.next;
            slow = slow.next;
        }
        return true;
    }
}
Linked List Cycle II Problem

Given a linked list, return the node where the cycle begins.

If there is no cycle, return null.

Example

Given -21->10->4->5, tail connects to node index 1，return 10.

Note

畫一個(gè)簡(jiǎn)圖：

a: length of non-loop 非環(huán)直線的長(zhǎng)度
b: length of loop     環(huán)的長(zhǎng)度
x: the point slow and fast meet in the loop 快慢指針在環(huán)內(nèi)相遇的位置

--------oooo
        o  o
        ooxo

(a+x)*2 = a-1+kb+x --> a = kb-1-x, slow needs to go kb-x longer to finish the loop.
so if head wants to go to the start point of the loop, it would pass a, the same for slow. After head went a, slow went kb-x-1. However, a = kb-x-1, so head is slow.next at the loop, which is the start point of the loop.

slow在fast在環(huán)里的k處相遇，fast比slow走了兩倍的路程，假設(shè)非環(huán)路和環(huán)路長(zhǎng)度分別為a和b，且fast已經(jīng)在環(huán)里多走了k圈，所以：
(a+x)*2 = a-1+kb+x --> a = kb-1-x
此時(shí)，slow還要走kb-x才能走完整個(gè)環(huán)。
而讓head此時(shí)重新從起點(diǎn)出發(fā)，以和slow相同的速度，需要走非環(huán)路的直線長(zhǎng)度a，才能到達(dá)環(huán)的起點(diǎn)。
那么，head到達(dá)環(huán)的時(shí)候，走了a = kb-1-x：是slow在環(huán)內(nèi)走到環(huán)的起點(diǎn)的路程-1。
也就是說(shuō)，slow.next = head，就是第二個(gè)while循環(huán)結(jié)束的條件。

Solution 
public class Solution {
    public ListNode detectCycle(ListNode head) {  
        if (head == null) return null;
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast != slow) {
            if (fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
        }
        while (head != slow.next) {
            head = head.next;
            slow = slow.next;
        }
        return head;
    }
}

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

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

相關(guān)文章

  • leetcode141-142. Linked List Cycle I & II

    摘要：題目要求這道題目要求判斷一個(gè)鏈表中是否有環(huán)，如果有環(huán)，就返回環(huán)中的第一個(gè)節(jié)點(diǎn)。如果有環(huán)，就會(huì)重復(fù)遇到這個(gè)指向的節(jié)點(diǎn)。則該鏈表有環(huán)，且該節(jié)點(diǎn)就是環(huán)的起始節(jié)點(diǎn)。但是這個(gè)方法會(huì)毀壞原來(lái)鏈表的數(shù)據(jù)結(jié)構(gòu)。 題目要求 Given a linked list, return the node where the cycle begins. If there is no cycle, return n...

    張巨偉 評(píng)論0 收藏0

  • 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] Reverse Linked List I & II

    Reverse Linked List Reverse a singly linked list. Note Create tail = null; Head loop through the list: Store head.next, head points to tail, tail becomes head, head goes to stored head.next; Return t...

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

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

0條評(píng)論

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