2181、[中等] 合并零之間的節點

1、問題描述：

給你一個鏈表的頭節點 head ，該鏈表包含由 0 分隔開的一連串整數。鏈表的 開端 和 末尾 的節點都滿足 Node.val == 0 。

對于每兩個相鄰的 0 ，請你將它們之間的所有節點合并成一個節點，其值是所有已合并節點的值之和。然后將所有 0 移除，修改后的鏈表不應該含有任何 0 。

返回修改后鏈表的頭節點 head 。

2、代碼思路：

1. 跳過第一個節點：鏈表的開頭和結尾都包含值為 0 的節點，我們從第二個節點開始處理（即 head->next）。
2. 累加節點值：對于每兩個 0 之間的節點，累加它們的值。
3. 遇到 0 時創建新節點：當遇到 0 時，將前面累加的值創建一個新的節點，插入到新鏈表中。
4. 繼續遍歷：繼續遍歷鏈表，重復上述步驟，直到遍歷完整個鏈表。返回合并后的新鏈表，忽略初始的哨兵節點。

3、代碼實現與詳細注釋

class Solution {
public:ListNode* mergeNodes(ListNode* head) {// 創建一個新的鏈表頭，用來存儲合并后的結果鏈表ListNode newhead; // 一個新鏈表的頭節點（哨兵節點）ListNode *newcur = &newhead; // 用于遍歷新鏈表的指針，初始化指向哨兵節點ListNode *cur = head->next;  // 當前鏈表從 head->next 開始，因為 head 是 0，忽略它int sum = 0; // 用于累加兩個 0 之間的節點的值// 遍歷原始鏈表，直到結束while (cur) {// 遇到值為 0 的節點時，說明需要合并并創建新節點if (cur->val == 0) {// 創建新節點，節點值為前面累加的 sum 值ListNode* newnode = new ListNode(sum);sum = 0; // 重置 sum，準備下一組合并newcur->next = newnode; // 將新節點鏈接到結果鏈表newcur = newcur->next;  // 移動指針到新節點，準備接受下一個合并節點} else {// 如果不是 0，則累加當前節點的值sum += cur->val;}cur = cur->next; // 移動到下一個節點}// 確保新鏈表的末尾指向 nullptrnewcur->next = nullptr;// 返回合并后鏈表的頭節點，跳過哨兵節點return newhead.next;}
};

4、時間復雜度：

• 時間復雜度：O(n)，其中 n 是鏈表中節點的數量。我們只需要遍歷鏈表一次。
• 空間復雜度：O(1)，只用了常數空間來存儲累加值和指針。