摘要:如果鏈表無環,則返回。為了表示給定鏈表中的環,我們使用整數來表示鏈表尾連接到鏈表中的位置索引從開始。說明不允許修改給定的鏈表。
題目地址:
https://leetcode-cn.com/probl...
題目描述:
給定一個鏈表,返回鏈表開始入環的第一個節點。 如果鏈表無環,則返回 null。
為了表示給定鏈表中的環,我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置(索引從 0 開始)。 如果 pos 是 -1,則在該鏈表中沒有環。
說明:不允許修改給定的鏈表。
解答:
判斷一個鏈表有沒有環是一個固定的套路,用快慢雙指針,一開始兩者都指向head節點,快指針一次走2步,而慢指針一次走1步,如果兩者相遇,那么就會有環。(注意的是這里只需要判斷快指針的空指針問題,因為如果沒有環一定是快指針先到尾部,所以不需要在意慢指針的為空情況。)
找環的入口節點也是一個固定的套路。當快慢指針相遇之后,重新設置一個慢指針到頭節點,然后這個指針和剛才的慢指針一起向后移動,直到兩者相遇,返回相遇點就是答案。
java ac代碼:
/** * 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)return null; ListNode p1 = head,p2 = head; while(true) { for(int i = 0;i < 2;i++) if(p2.next!= null) p2 = p2.next; else return null; p1 = p1.next; if(p1 == p2) { p1 = head; while(p1 != p2) { p1 = p1.next; p2 = p2.next; } return p1; } } } }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/73025.html
摘要:圖因此可以成為樹,在所有可能的樹中,具有最小高度的樹被稱為最小高度樹。給出這樣的一個圖,寫出一個函數找到所有的最小高度樹并返回他們的根節點。因此使用一個數組代表每個節點的入度,若入度為就是葉子節點。 題目地址:https://leetcode-cn.com/probl...題目描述: 對于一個具有樹特征的無向圖,我們可選擇任何一個節點作為根。圖因此可以成為樹,在所有可能的樹中,具有最小...
摘要:關于遞歸這里提一兩點遞歸基本有這幾步遞歸的模板,終止條件,遞歸調用,邏輯處理。 ?作者簡介:大家好,我是車神哥,府學路18號的車神? ?個人主頁:應無所住而生...
閱讀 2101·2021-11-18 10:02
閱讀 2850·2021-09-04 16:41
閱讀 1142·2019-08-30 15:55
閱讀 1405·2019-08-29 17:27
閱讀 1069·2019-08-29 17:12
閱讀 2535·2019-08-29 15:38
閱讀 2855·2019-08-29 13:02
閱讀 2831·2019-08-29 12:29