MediumRating 1455
2487. Remove Nodes From Linked List
linked-liststackrecursionmonotonic-stack
解題說明
Remove Nodes From Linked List
題目描述： 給定一個鏈結串列，移除所有右邊存在更大值的節點。也就是說，只保留那些從該節點到尾端沒有比它更大的值的節點。
解題思路： 從右往左看，我們需要維護一個「從右邊看到的最大值」。任何小於此最大值的節點都要被移除。
最直觀的做法是使用單調遞減棧：從左到右遍歷鏈結串列，維護一個遞減棧。對於每個節點，彈出棧中所有值小於當前節點值的節點（因為這些節點右邊存在更大值）。最後棧中剩下的就是答案。
也可以反轉鏈結串列，從頭開始維護最大值，然後再反轉回來。
C++ 解法
複雜度分析
時間複雜度：O(n) — 每個節點最多被壓入和彈出棧各一次
空間複雜度：O(n) — 棧最多儲存 n 個節點
虛擬碼
1. Initialize empty stack
2. Traverse linked list from head:
a. While stack is not empty and top's value < current value:
- Pop stack (this node has a larger value to its right)
b. Push current node onto stack
3. Reconstruct list from stack:
a. Pop nodes one by one, linking each to the previous
b. Return the last popped node as new head其他解法
-
反轉鏈結串列法：(a) 反轉鏈結串列，(b) 從頭遍歷，維護當前最大值，移除所有小於最大值的節點，(c) 再次反轉。時間 O(n)，空間 O(1)（不需要棧）。
-
遞迴法：遞迴到尾端，返回時維護右側最大值。若當前值 < 右側最大值則跳過該節點。時間 O(n)，空間 O(n)（遞迴棧）。程式碼最簡潔但有遞迴深度限制。
延伸思考
- 如果改為移除「左邊存在更大值」的節點，演算法如何簡化？
- 如果要移除「左邊或右邊存在更大值」的節點（兩側都考慮），如何設計？
- 如果鏈結串列是雙向鏈結串列，反轉法的空間是否可以進一步優化？