142. Linked List CycleII

Developer 發(fā)布于2019-08-14 14:20 / 1454人閱讀

摘要：題目解答當(dāng)與相遇的時候，比多了一圈，而也正好走了一圈。但是原來走的是圈外的路，從起點到圈開始的路，所以在實際圈里剩下的路程，其實就是從起點到圈開始的點的距離。

題目：
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?

解答：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            //當(dāng)slow與fast相遇的時候，fast比slow多了一圈，而slow也正好走了一圈。但是slow原來走的是圈外的路，從起點到圈開始的路，所以在實際圈里剩下的路程，其實就是從起點到圈開始的點的距離。那么我們設(shè)一個點slow2開始從起點走，走到slow2和slow相遇的時候，就是圈開始的點了
            if (slow == fast) {
                ListNode slow2 = head;
                while (slow2 != slow) {
                    slow2 = slow2.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
    }
}

云服務(wù)器 GPU云服務(wù)器 CycleII linked cdn142 list

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

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64949.html

相關(guān)文章

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
leetcode141-142. Linked List Cycle I & II

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

張巨偉 2019-08-16 10:40 評論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)142

摘要：如果鏈表無環(huán)，則返回。為了表示給定鏈表中的環(huán)，我們使用整數(shù)來表示鏈表尾連接到鏈表中的位置索引從開始。說明不允許修改給定的鏈表。題目地址：https://leetcode-cn.com/probl...題目描述：給定一個鏈表，返回鏈表開始入環(huán)的第一個節(jié)點。如果鏈表無環(huán)，則返回 null。為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）...

DevTTL 2019-08-16 14:29 評論0 收藏0