資訊專欄INFORMATION COLUMN
摘要：快慢指針法復(fù)雜度時間空間思路這是一道非常經(jīng)典的雙指針題。如果快指針和慢指針相遇，則說明鏈表有環(huán)。代碼快慢指針法復(fù)雜度時間空間思路這題是基于上一題，上一題我們發(fā)現(xiàn)相遇后就返回了，而這里我們還要繼續(xù)找到環(huán)的起始點(diǎn)。
Linked List Cycle I
Given a linked list, determine if it has a cycle in it.快慢指針法 復(fù)雜度Follow up: Can you solve it without using extra space?
時間 O(N) 空間 O(1)
思路這是一道非常經(jīng)典的雙指針題。我們從頭設(shè)置一個快指針，一個慢指針?？熘羔樢淮巫邇刹剑羔樢淮巫咭徊?，如果快指針走到了盡頭，則說明鏈表無環(huán)。如果快指針和慢指針相遇，則說明鏈表有環(huán)。為什么相遇就說明有環(huán)呢？設(shè)想一個有環(huán)鏈表，快慢指針最后都會走到環(huán)上，而這個環(huán)就像一個環(huán)形跑道一樣，慢指針在后面，快指針在前面，但實(shí)際上快指針也在追慢指針，希望能超慢指針一圈。他們在這個跑道上，總會有一天快指針追上了慢指針。我們不用擔(dān)心快指針跳過了慢指針，因?yàn)樗麄儍傻乃俣炔钍?，所以她們倆在環(huán)上的距離總是每次減1，最后總能減到0。
代碼public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(fast == slow){
return true;
}
}
return false;
}
}
2018/10
func hasCycle(head *ListNode) bool {
fast := head
slow := head
// if fast.Next == nil and fast != slow, there can"t be a cycle
for fast != nil && fast.Next != nil {
fast = fast.Next.Next
slow = slow.Next
if fast == slow {
return true
}
}
return false
}
Linked List Cycle II
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.快慢指針法 復(fù)雜度Note: Do not modify the linked list.
Follow up: Can you solve it without using extra space?
時間 O(N) 空間 O(1)
思路這題是基于上一題，上一題我們發(fā)現(xiàn)相遇后就返回true了，而這里我們還要繼續(xù)找到環(huán)的起始點(diǎn)。假設(shè)快慢指針在環(huán)上第k個節(jié)點(diǎn)相遇，而環(huán)的起點(diǎn)是鏈表第m個節(jié)點(diǎn)，環(huán)的總長度是n。此時慢指針再走n-k步就回到了環(huán)的開頭，而此時快指針已經(jīng)走了m+k步。如果我們這時候?qū)⒖熘羔樂呕仄瘘c(diǎn)，并讓它也一次走1步，這樣當(dāng)兩個節(jié)點(diǎn)再次相遇時，相遇點(diǎn)就是環(huán)的起點(diǎn)。
代碼public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
// 找相遇點(diǎn)
slow = head;
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64487.html
摘要：說明不允許修改給定的鏈表。算法思路題目要求返回單鏈表中存在循環(huán)鏈表的位置。首先，先判斷該單鏈表是否存在循環(huán)鏈表用兩個快慢指針分別指向鏈表的頭部，每次移動兩步，每次移動一步，移動的步數(shù)是的兩倍。 Time：2019/4/8Title: Linked List Cycle IIDifficulty: mediumAuthor:小鹿 題目：Linked List Cycle II Giv...
摘要：如果鏈表無環(huán)，則返回。說明不允許修改給定的鏈表。示例輸入輸出解釋鏈表中有一個環(huán)，其尾部連接到第一個節(jié)點(diǎn)。兩種方法哈希表哈希表添加節(jié)點(diǎn)時只要發(fā)現(xiàn)節(jié)點(diǎn)已經(jīng)存在了，證明就有環(huán)形鏈表。 給定一個鏈表，返回鏈表開始入環(huán)的第一個節(jié)點(diǎn)。 如果鏈表無環(huán)，則返回 null。 為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該...
摘要：如果鏈表無環(huán)，則返回。說明不允許修改給定的鏈表。示例輸入輸出解釋鏈表中有一個環(huán)，其尾部連接到第一個節(jié)點(diǎn)。兩種方法哈希表哈希表添加節(jié)點(diǎn)時只要發(fā)現(xiàn)節(jié)點(diǎn)已經(jīng)存在了，證明就有環(huán)形鏈表。 給定一個鏈表，返回鏈表開始入環(huán)的第一個節(jié)點(diǎn)。 如果鏈表無環(huán)，則返回 null。 為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該...
摘要：給定一個鏈表，判斷鏈表中是否有環(huán)。示例輸入輸出解釋鏈表中有一個環(huán)，其尾部連接到第一個節(jié)點(diǎn)。哈希表解決重復(fù)問題最容易想到的數(shù)據(jù)結(jié)構(gòu)就是哈希表，哈希表添加節(jié)點(diǎn)時只要發(fā)現(xiàn)節(jié)點(diǎn)已經(jīng)存在了，證明就有環(huán)形鏈表。 給定一個鏈表，判斷鏈表中是否有環(huán)。 為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該鏈表中沒有環(huán)。 Giv...
摘要：給定一個鏈表，判斷鏈表中是否有環(huán)。示例輸入輸出解釋鏈表中有一個環(huán)，其尾部連接到第一個節(jié)點(diǎn)。哈希表解決重復(fù)問題最容易想到的數(shù)據(jù)結(jié)構(gòu)就是哈希表，哈希表添加節(jié)點(diǎn)時只要發(fā)現(xiàn)節(jié)點(diǎn)已經(jīng)存在了，證明就有環(huán)形鏈表。 給定一個鏈表，判斷鏈表中是否有環(huán)。 為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該鏈表中沒有環(huán)。 Giv...
閱讀 1356·2021-11-25 09:43
閱讀 777·2021-11-18 10:02
閱讀 2923·2021-09-07 09:59
閱讀 2787·2021-08-30 09:44
閱讀 2945·2019-08-30 13:17
閱讀 2341·2019-08-29 12:17
閱讀 1702·2019-08-28 17:57
閱讀 1317·2019-08-26 14:04
