此題屬于中低難度的題，思路并不複雜，單其中有很多易錯點，比如空指針判斷、指針丢失等；

思路：設置三個指針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);

}

鍊表歸并排序比數組歸并排序難度有所增加，但思路是一緻的，仍然是逐步分解，直到隻有一個結點，然後再合并。

主要區别在于中點的選取，關于中點選取，這裡也有現成的思路，通過快慢指針，當快指針走到終點時，慢指針即為中點。

具體實現如下：

連載系列：

技術連載：開篇詞

技術連載：連載提綱設計思路

技術連載：數據結構 - 數組

技術連載：數據結構 - 數組常見面試題彙總

技術連載：數據結構 - 鍊表

,

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!

查看全部