[Leetcode] 86. Partition List (分隔鏈表) 題解紀錄

題目:

Partition list (分隔鏈表)

難度:

中等

題目要求:

題目給定一組鏈表和一個目標值(x)，需要返回一組鏈表，鏈表中小於 x 的節點都會出現在大的節點之前，並且保留鏈表中節點的初始相對位置

解題思路:

這題主要的解法是用兩個鏈表作為儲存，一個鏈表儲存小於 x 節點，一個鏈表儲存大於 x 的節點，最終再把兩個鏈表作合併就會是答案了

下面有幾的地方需要注意

1. 儲存的鏈表需要設置虛擬頭節點
   
   因為需要照順序來排序鏈表，所以需要創建虛擬頭節點來指向每個節點的( next )
2. 需要宣告指針來操作儲存的鏈表
   
   主要是因為最後一段在拚湊和返回鏈表的時候，需要使用到頭部節點和尾部節點，使用指針的話，就可以在迴圈完成後同時訪問鏈表的頭部節點和尾部節點，做拼湊和返回的操作

這題的時間複雜度為 O(n)，空間複雜度也為 O(n)