🔗 🟡 2181. Merge Nodes in Between Zeros 1333

tags: `Weekly Contest 281` `鏈結串列(Linked List)` `模擬(Simulation)`

題意

給定一個鏈結串列(Linked List) 的第一個節點 $head$ ，其中包含一系列以 $0$ 分隔的整數，且鏈結串列的開頭和結尾都滿足 $node.val == 0$ 。

對於相鄰的每兩個 $0$ ，將它們之間的所有節點合併為一個節點，其值為所有已合併節點的和。然後將所有 $0$ 移除，修改後的鏈結串列不應包含任何 $0$ 。

返回修改後的鏈結串列的頭節點 $head$ 。

思路：模擬(Simulation)

根據題意，若 Linked List 中有 $m + 1$ 個節點為 $0$ ，則需返回包含 $m$ 個節點的新 Linked List。

我們可以先將所有 $0$ 節點保留，並在計算完中間節點的和後，將其保存到後面的那個 $0$ 節點中，然後將前面的 $0$ 節點連接到後面的 $0$ 節點，最後去除第一個 $0$ 節點即可。

具體步驟如下：

初始化兩個指標 $pre$ $p re$ 和 $cur$ $c u r$ 。 $pre$ $p re$ 用於指向上一次出現值為 $0$ $0$ 的節點， $cur$ $c u r$ 用於遍歷鏈結串列。
- 由於題目確保第一個節點的值為 $0$ ，因此初始化 $pre = head$ 。
- $cur$ 指向 $head$ 的下一個節點 $head.next$ 。
使用一個變數 $s$ 來累加兩個 $0$ 節點之間的節點值，初始化 $s = 0$ 。
遍歷鏈結串列，對於每個節點：
- 如果節點值為 $0$ $0$ ，表示找到了一段需要合併的區間。此時：
  - 將當前節點的值設置為 $s$ ，並將 $s$ 重置為 $0$ 。
  - 將 $pre.next$ 指向當前節點，以便移除中間的所有節點。
  - 將 $pre$ 更新為當前節點。
- 如果節點值不為 $0$ ，則累加 $s$ 。
最後返回修改後的鏈結串列的頭節點。注意，初始的第一個 $0$ 節點不需要，所以返回 $head.next$ 。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ ， $n$ 為鏈結串列的節點數量。
空間複雜度： $\mathcal{O}(1)$ 。

class Solution:
    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None: # for pylance
            return None
        pre = head # previous 0 node
        cur = head.next
        s = 0
        while cur:
            if cur.val == 0:
                cur.val = s
                s = 0
                pre.next = cur # connect the previous 0 node to the current node
                pre = cur
            else:
                s += cur.val
            cur = cur.next
        return head.next # the first 0 node is not needed

class Solution {
public:
    ListNode* mergeNodes(ListNode* head) {
        ListNode *pre = head, *cur = head->next;
        int s = 0;
        while (cur != nullptr) {
            if (cur->val == 0) {
                cur->val = s;
                s = 0;
                pre->next = cur;
                pre = cur;
            } else {
                s += cur->val;
            }
            cur = cur->next;
        }
        return head->next;
    }
};