資訊專欄INFORMATION COLUMN
摘要：題目要求這道題目要求判斷一個(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 null. Note: Do not modify the linked list. Follow up: Can you solve it without using extra space?
這道題目要求判斷一個(gè)鏈表中是否有環(huán)，如果有環(huán)，就返回環(huán)中的第一個(gè)節(jié)點(diǎn)。
判斷是否有環(huán)判斷是否有環(huán)有兩種方法，第一種是雙指針的方法，雙指針方法意味著快指針一定有一天會(huì)遇上慢指針，只要鏈表中有環(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é)果給拆掉，一旦遍歷過當(dāng)前節(jié)點(diǎn)，就將當(dāng)前節(jié)點(diǎn)的下一個(gè)指針指向dummy節(jié)點(diǎn)。如果有環(huán)，就會(huì)重復(fù)遇到這個(gè)指向dummy的節(jié)點(diǎn)。則該鏈表有環(huán)，且該節(jié)點(diǎn)就是環(huán)的起始節(jié)點(diǎn)。但是這個(gè)方法會(huì)毀壞原來鏈表的數(shù)據(jù)結(jié)構(gòu)。
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é)點(diǎn)
那么如何才能在環(huán)中找到起始節(jié)點(diǎn)呢？這就要找出雙指針之間運(yùn)動(dòng)的規(guī)律了。當(dāng)快慢指針第一次相遇時(shí)，我們假設(shè)慢指針和環(huán)中第一個(gè)節(jié)點(diǎn)距離為X，而環(huán)中第一個(gè)節(jié)點(diǎn)距離起始節(jié)點(diǎn)為Y。而因?yàn)榭熘羔樤谧吡艘蝗σ院笠餐Ａ粼谠摴?jié)點(diǎn)，因此快指針走過的總距離為(X+Y)*2。又因?yàn)榭炻羔樝嘤鰶Q定了快指針比慢指針多走了一圈，因此2(X+Y)-(X+Y)=CYCLE，也就是X+Y=CYCLE。這時(shí)我們可以知道如果再走Y步，慢指針就可以回到環(huán)中的第一個(gè)節(jié)點(diǎn)，而Y也恰好是環(huán)中第一個(gè)節(jié)點(diǎn)距離起始節(jié)點(diǎn)的位置。因此如果這時(shí)有另一個(gè)指針同時(shí)從起點(diǎn)出發(fā)，則二者相遇的地方就是環(huán)的起始節(jié)點(diǎn)。
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ā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會(huì)不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/70230.html
摘要：做法如果有環(huán)，快慢指針必定可以相遇。而讓此時(shí)重新從起點(diǎn)出發(fā)，以和相同的速度，需要走非環(huán)路的直線長度，才能到達(dá)環(huán)的起點(diǎn)。也就是說，，就是第二個(gè)循環(huán)結(jié)束的條件。 Linked List Cycle I Problem Given a linked list, determine if it has a cycle in it. Example Given -21->10->4->5, ta...
摘要：說明不允許修改給定的鏈表。算法思路題目要求返回單鏈表中存在循環(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...
摘要：如果鏈表無環(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，則在該...
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...
閱讀 2086·2023-04-25 19:15
閱讀 2265·2021-11-23 09:51
閱讀 1272·2021-11-17 09:33
閱讀 2177·2021-08-26 14:15
閱讀 2493·2019-08-30 15:54
閱讀 1590·2019-08-30 15:54
閱讀 2178·2019-08-30 12:50
閱讀 1143·2019-08-29 17:08
