leetcode141-142. Linked List Cycle I & II

張巨偉發布于2019-08-16 10:40 / 2175人閱讀

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

題目要求

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?

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

判斷是否有環

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

    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;
    }

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

    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;
    }

找到環的起始節點

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

    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;
    }

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

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

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

[LintCode] Linked List Cycle I &amp; II

摘要：做法如果有環，快慢指針必定可以相遇。而讓此時重新從起點出發，以和相同的速度，需要走非環路的直線長度，才能到達環的起點。也就是說，，就是第二個循環結束的條件。 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題 —— 環形鏈表 II（Linked Li

摘要：說明不允許修改給定的鏈表。算法思路題目要求返回單鏈表中存在循環鏈表的位置。首先，先判斷該單鏈表是否存在循環鏈表用兩個快慢指針分別指向鏈表的頭部，每次移動兩步，每次移動一步，移動的步數是的兩倍。 Time：2019/4/8Title: Linked List Cycle IIDifficulty: mediumAuthor:小鹿題目：Linked List Cycle II Giv...

whidy 2019-08-23 16:51 評論0 收藏0
LeetCode 142：環形鏈表 II Linked List Cycle II

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

hoohack 2019-08-16 18:36 評論0 收藏0
LeetCode 142：環形鏈表 II Linked List Cycle II

摘要：如果鏈表無環，則返回。說明不允許修改給定的鏈表。示例輸入輸出解釋鏈表中有一個環，其尾部連接到第一個節點。兩種方法哈希表哈希表添加節點時只要發現節點已經存在了，證明就有環形鏈表。給定一個鏈表，返回鏈表開始入環的第一個節點。如果鏈表無環，則返回 null。為了表示給定鏈表中的環，我們使用整數 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