嵌套娃娃 用遞迴解 串列化簡題 Leetcode #2487

Diver Zhang on Unsplash

題目敘述

輸入給定一個鏈結串列的head node。

要求我們進行化簡，只要某個節點的右手邊存在比較大的節點，就刪除掉。

例如 5->2->13->3

5的右手邊有13，所以5刪除掉。

2的右手邊有13，所以2刪除掉。

13的右手邊沒有更大的節點，所以13留著。

3的右手邊沒有更大的節點，所以3留著。

最後輸出為13->3。

原本的英文題目敘述

測試範例

Example 1:

Input: head = [5,2,13,3,8]
Output: [13,8]
Explanation: The nodes that should be removed are 5, 2 and 3.
- Node 13 is to the right of node 5.
- Node 13 is to the right of node 2.
- Node 8 is to the right of node 3.

Example 2:

Input: head = [1,1,1,1]
Output: [1,1,1,1]
Explanation: Every node has value 1, so no nodes are removed.

約束條件

 Constraints:

• The number of the nodes in the given list is in the range [1, 10^5].

節點總數目介於 1 ~ 十萬之間。

• 1 <= Node.val <= 10^5

每個節點的節點值也介於 1 ~ 十萬之間。

演算法 DFS遞迴解

這題的關鍵其實就隱藏在化簡規則裡。

題目說:

某個節點的右手邊只要有比較大的節點，就刪除掉。

白話講，可以這麼說，通則就是

如果右邊有人比我(當下的節點)還大，則只保留右邊(相當於下個鄰居)。

如果右邊沒有人比我大，則我自己保留下來，並且保留原本的連接。

初始條件，也可以說 終止條件，什麼時候停下來?

當遇到空節點的時候，代表已經拜訪到串列的尾端，化簡流程結束。

示意圖

程式碼 DFS遞迴解

class Solution:
    def removeNodes(self, head):
        
        ## Base case:
        # Empty node or empty list
        if not head:
            return head
        
        ## General cases:
        # Use the same pattern to carry out reduction
        head.next = self.removeNodes(head.next)

        # Next neighbor is larger than me, then keep neighbor alive
        if head.next and head.next.val > head.val:
            return head.next
        else:
        # Next neighbor is smaller than or equal to me, then keep myself alive
            return head

複雜度分析

時間複雜度: O(n)

線性掃描，從左到右掃描每個節點，總共耗時O(n)

空間複雜度: O(n)

線性掃描，從左到右掃描每個節點，遞迴call stack最大深度為O(n)

關鍵知識點

這題的關鍵其實就隱藏在化簡規則裡。

題目說:

某個節點的右手邊只要有比較大的節點，就刪除掉。

白話講，可以這麼說，通則就是

如果右邊有人比我(當下的節點)還大，則只保留右邊(相當於下個鄰居)。

如果右邊沒有人比我大，則我自己保留下來，並且保留原本的連接。

Reference:

[1] Remove Nodes From Linked List - LeetCode