此題屬于中低難度的題,思路并不複雜,單其中有很多易錯點,比如空指針判斷、指針丢失等;
思路:設置三個指針pre、cur、next,初始時刻pre = null,cur = head;
開始處理,首先執行next = cur.next,防止後面cur.next修改之後指針丢失;
鍊表反轉
環形鍊表檢測并返回入環點這個題目技巧性很強,一般不太容易想到;大體思路如下:
首先設置快慢指針,每一次移動,快指針移動兩步(尤其需要注意第二步判斷空指針),慢指針移動移步;然後判斷兩個指針是否指向同一位置。
如果最終快指針遇見null,則無環;如果快慢指針指向了同一位置,則有環;
如果有環的化,兩指針相遇時,快指針移動到head位置,并且變為慢指針(每次移動一步);然後兩個指針再次開始移動,直到再次相遇即為入環點。(證明略)
環形鍊表檢測
鍊表歸并排序二路歸并排序:假設兩個有序數組,設置兩個指針,指向0位置,将指向比較小元素的指針對應的元素存入數組,并移動指針;直到兩個指針移動完畢;
歸并排序思路:歸并排序是建立在二路歸并排序基礎之上,将數組逐漸分解,直到僅有一個元素,然後進行二路歸并排序。(先分後合的思想)
僞代碼如下:
public int[] merge(int[] nums,int start, int end){
if(start == end){
return new int[]{nums[start]};
}
int mid = (start end) / 2;
int[] s1 = merge(nums, start,mid);
int[] s2 = merge(nums,mid 1, end);
return binMerge(s1,s2);
}
鍊表歸并排序比數組歸并排序難度有所增加,但思路是一緻的,仍然是逐步分解,直到隻有一個結點,然後再合并。
主要區别在于中點的選取,關于中點選取,這裡也有現成的思路,通過快慢指針,當快指針走到終點時,慢指針即為中點。
具體實現如下:
連載系列:
技術連載:開篇詞
技術連載:連載提綱設計思路
技術連載:數據結構 - 數組
技術連載:數據結構 - 數組常見面試題彙總
技術連載:數據結構 - 鍊表
,