題目敘述 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)
