leetcode141-142. Linked List Cycle I & II

張巨偉發(fā)布于2019-08-16 10:40 / 2182人閱讀

摘要：題目要求這道題目要求判斷一個鏈表中是否有環(huán)，如果有環(huán)，就返回環(huán)中的第一個節(jié)點。如果有環(huán)，就會重復遇到這個指向的節(jié)點。則該鏈表有環(huán)，且該節(jié)點就是環(huán)的起始節(jié)點。但是這個方法會毀壞原來鏈表的數(shù)據(jù)結構。

題目要求

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?

這道題目要求判斷一個鏈表中是否有環(huán)，如果有環(huán)，就返回環(huán)中的第一個節(jié)點。

判斷是否有環(huán)

判斷是否有環(huán)有兩種方法，第一種是雙指針的方法，雙指針方法意味著快指針一定有一天會遇上慢指針，只要鏈表中有環(huán)。

    public boolean hasCycle(ListNode head) {
        if(head==null) return false;
        ListNode walker = head, runner = head;
        while(runner.next!=null && runner.next.next!=null){
            walker = walker.next;
            runner = runner.next.next;
            if(walker==runner) return true;
        }
        return false;
    }

還有一種方法是指將鏈表的結果給拆掉，一旦遍歷過當前節(jié)點，就將當前節(jié)點的下一個指針指向dummy節(jié)點。如果有環(huán)，就會重復遇到這個指向dummy的節(jié)點。則該鏈表有環(huán)，且該節(jié)點就是環(huán)的起始節(jié)點。但是這個方法會毀壞原來鏈表的數(shù)據(jù)結構。

    public boolean hasCycle2(ListNode head){
        if(head==null) return false;
        ListNode dummy = new ListNode(0);
        while(head.next!=null){
            if(head.next==dummy)return true;
            ListNode temp = head.next;
            head.next = dummy;
            head = temp;
        }
        return false;
    }

找到環(huán)的起始節(jié)點

那么如何才能在環(huán)中找到起始節(jié)點呢？這就要找出雙指針之間運動的規(guī)律了。當快慢指針第一次相遇時，我們假設慢指針和環(huán)中第一個節(jié)點距離為X，而環(huán)中第一個節(jié)點距離起始節(jié)點為Y。而因為快指針在走了一圈以后也停留在該節(jié)點，因此快指針走過的總距離為(X+Y)*2。又因為快慢指針相遇決定了快指針比慢指針多走了一圈，因此2(X+Y)-(X+Y)=CYCLE，也就是X+Y=CYCLE。這時我們可以知道如果再走Y步，慢指針就可以回到環(huán)中的第一個節(jié)點，而Y也恰好是環(huán)中第一個節(jié)點距離起始節(jié)點的位置。因此如果這時有另一個指針同時從起點出發(fā)，則二者相遇的地方就是環(huán)的起始節(jié)點。

    public ListNode detectCycle(ListNode head) {
        if(head==null) return null;
        ListNode runner = head, walker = head;
        while(runner.next!=null && runner.next.next!=null){
            walker = walker.next;
            runner = runner.next.next;
            if(walker==runner){
                ListNode temp = head;
                while(temp!=walker){
                    temp = temp.next;
                    walker = walker.next;
                }
                return temp;
            }
        }
        
        return null;
    }

想要了解更多開發(fā)技術，面試教程以及互聯(lián)網(wǎng)公司內推，歡迎關注我的微信公眾號！將會不定期的發(fā)放福利哦~

GPU云服務器云服務器 list&ampamp list&amplt II ii6

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

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

[LintCode] Linked List Cycle I &amp; II

摘要：做法如果有環(huán)，快慢指針必定可以相遇。而讓此時重新從起點出發(fā)，以和相同的速度，需要走非環(huán)路的直線長度，才能到達環(huán)的起點。也就是說，，就是第二個循環(huán)結束的條件。 Linked List Cycle I Problem Given a linked list, determine if it has a cycle in it. Example Given -21->10->4->5, ta...

用戶83 2019-08-14 15:17 評論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 2019-08-23 16:51 評論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 2019-08-16 18:36 評論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 2019-07-31 11:29 評論0 收藏0
[LeetCode] Reverse Linked List I &amp; 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 2019-08-14 14:55 評論0 收藏0