摘要:題目解答當(dāng)與相遇的時(shí)候,比多了一圈,而也正好走了一圈。但是原來走的是圈外的路,從起點(diǎn)到圈開始的路,所以在實(shí)際圈里剩下的路程,其實(shí)就是從起點(diǎn)到圈開始的點(diǎn)的距離。
題目:
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相遇的時(shí)候,fast比slow多了一圈,而slow也正好走了一圈。但是slow原來走的是圈外的路,從起點(diǎn)到圈開始的路,所以在實(shí)際圈里剩下的路程,其實(shí)就是從起點(diǎn)到圈開始的點(diǎn)的距離。那么我們?cè)O(shè)一個(gè)點(diǎn)slow2開始從起點(diǎn)走,走到slow2和slow相遇的時(shí)候,就是圈開始的點(diǎn)了 if (slow == fast) { ListNode slow2 = head; while (slow2 != slow) { slow2 = slow2.next; slow = slow.next; } return slow; } } return null; } }
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/64949.html
摘要:說明不允許修改給定的鏈表。算法思路題目要求返回單鏈表中存在循環(huán)鏈表的位置。首先,先判斷該單鏈表是否存在循環(huán)鏈表用兩個(gè)快慢指針分別指向鏈表的頭部,每次移動(dòng)兩步,每次移動(dòng)一步,移動(dòng)的步數(shù)是的兩倍。 Time:2019/4/8Title: Linked List Cycle IIDifficulty: mediumAuthor:小鹿 題目:Linked List Cycle II Giv...
摘要:題目要求這道題目要求判斷一個(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ì)毀壞原來鏈表的數(shù)據(jù)結(jié)構(gòu)。 題目要求 Given a linked list, return the node where the cycle begins. If there is no cycle, return n...
摘要:如果鏈表無環(huán),則返回。說明不允許修改給定的鏈表。示例輸入輸出解釋鏈表中有一個(gè)環(huán),其尾部連接到第一個(gè)節(jié)點(diǎn)。兩種方法哈希表哈希表添加節(jié)點(diǎn)時(shí)只要發(fā)現(xiàn)節(jié)點(diǎn)已經(jīng)存在了,證明就有環(huán)形鏈表。 給定一個(gè)鏈表,返回鏈表開始入環(huán)的第一個(gè)節(jié)點(diǎn)。 如果鏈表無環(huán),則返回 null。 為了表示給定鏈表中的環(huán),我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置(索引從 0 開始)。 如果 pos 是 -1,則在該...
摘要:如果鏈表無環(huán),則返回。說明不允許修改給定的鏈表。示例輸入輸出解釋鏈表中有一個(gè)環(huán),其尾部連接到第一個(gè)節(jié)點(diǎn)。兩種方法哈希表哈希表添加節(jié)點(diǎn)時(shí)只要發(fā)現(xiàn)節(jié)點(diǎn)已經(jīng)存在了,證明就有環(huán)形鏈表。 給定一個(gè)鏈表,返回鏈表開始入環(huán)的第一個(gè)節(jié)點(diǎn)。 如果鏈表無環(huán),則返回 null。 為了表示給定鏈表中的環(huán),我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置(索引從 0 開始)。 如果 pos 是 -1,則在該...
摘要:如果鏈表無環(huán),則返回。為了表示給定鏈表中的環(huán),我們使用整數(shù)來表示鏈表尾連接到鏈表中的位置索引從開始。說明不允許修改給定的鏈表。 題目地址:https://leetcode-cn.com/probl...題目描述:給定一個(gè)鏈表,返回鏈表開始入環(huán)的第一個(gè)節(jié)點(diǎn)。 如果鏈表無環(huán),則返回 null。 為了表示給定鏈表中的環(huán),我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置(索引從 0 開始)...
閱讀 2123·2023-04-25 14:56
閱讀 2441·2021-11-16 11:44
閱讀 2696·2021-09-22 15:00
閱讀 1903·2019-08-29 16:55
閱讀 2177·2019-08-29 14:04
閱讀 2305·2019-08-29 11:23
閱讀 3678·2019-08-26 10:46
閱讀 1908·2019-08-22 18:43