[LeetCode] 143. Reorder List

轉自LeetCode

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

<Solution>
這題一開始想到的方式是用 recursive 來解，但會 TLE，必須用其它想法

想法如下

• 利用快慢指針，找到 list 的中間點，然後斷開，形成前後兩個 list

• 將後半段的 list 做反轉

• 將反轉後的 list，間隔地插入前半段的 list

code 如下(參考資料)

c++

還有一種解法

可以先將 node 都放到一個 stack，這樣也會知道整個 list 的長度

然後只需要將 (stack.size - 1) / 2 個 node 從 stack 拿出來，按照題目要求重新接上 list 即可

因為是用 stack ，所以也達到從後面的 node 反轉的效果

Kotlin