串列應用: 合併非零的節點 Merge Nodes in Between Zeros_Leetcode #2181

Andre Frueh on Unsplash

題目敘述 Merge Nodes in Between Zeros

給定一個鏈結串列，合併非零區間的節點(以加總的方式合併)，輸出合併後的鏈結串列。

測試範例

Example 1:

Input: head = [0,3,1,0,4,5,2,0]
Output: [4,11]
Explanation: 
The above figure represents the given linked list. The modified list contains
- The sum of the nodes marked in green: 3 + 1 = 4.
- The sum of the nodes marked in red: 4 + 5 + 2 = 11.

Example 2:

Input: head = [0,1,0,3,0,2,2,0]
Output: [1,3,4]
Explanation: 
The above figure represents the given linked list. The modified list contains
- The sum of the nodes marked in green: 1 = 1.
- The sum of the nodes marked in red: 3 = 3.
- The sum of the nodes marked in yellow: 2 + 2 = 4.

約束條件

Constraints:

• The number of nodes in the list is in the range [3, 2 * 10^5].

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

• 0 <= Node.val <= 1000

節點值都介於0~1000 之間。

• There are no two consecutive nodes with Node.val == 0.

不會有兩個相鄰的zero nodes

• The beginning and end of the linked list have Node.val == 0.

第一個節點 和 最後一個節點保證是0

演算法 找出合併規律

如果現在這個節點的節點值非零，就持續累加節點值，直到遇到zero node為止。

如果現在這個節點的節點值為零，則把加總的值更新到前一個節點prev上，接著啟動下一次的合併流程，直到遇到整條串列的尾端為止。

程式碼 找出合併規律

class Solution:
    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:

        def merge(prev, cur, val):

            if cur.val == 0:
                # Merge nodes between 0s
                prev.val = val

                if cur.next is None:
                    # Tail node
                    prev.next = None
                else:
                    # Non-tail node
                    prev.next = cur
                    merge(cur, cur.next, 0)
            else:
                # Keep accumulate value of node
                merge(prev, cur.next, val+cur.val)

        #---------------------------------
        merge(head, head.next, 0)
        return head

複雜度分析

時間複雜度: O(n)

從頭到尾，每個節點拜訪一次，並且在過程中合併非零節點。

空間複雜度: O(n)

從頭到尾，每個節點拜訪一次，並且在過程中合併非零節點。
DFS call stack深度最深為O(n)

Reference

[1] Merge Nodes in Between Zeros - LeetCode