1. 題目

給你一個鏈表的頭節點 head，請你編寫代碼，反復刪去鏈表中由 總和 值為 0 的連續節點組成的序列，直到不存在這樣的序列為止。

刪除完畢后，請你返回最終結果鏈表的頭節點。

你可以返回任何滿足題目要求的答案。

（注意，下面示例中的所有序列，都是對 ListNode 對象序列化的表示。）示例 1： 輸入：head = [1,2,-3,3,1] 輸出：[3,1] 提示：答案 [1,2,1] 也是正確的。示例 2： 輸入：head = [1,2,3,-3,4] 輸出：[1,2,4]示例 3： 輸入：head = [1,2,3,-3,-2] 輸出：[1]提示： 給你的鏈表中可能有 1 到 1000 個節點。 對于鏈表中的每個節點，節點的值：-1000 <= node.val <= 1000.

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 哈希表

• 建立包含當前節點的前綴和sum為Key，當前節點指針為Value的哈希表
• 當sum在哈希表中存在時，兩個sum之間的鏈表可以刪除
• 先將中間的要刪除段的哈希表清除，再斷開鏈表
• 循環執行以上步驟

class Solution { public:ListNode* removeZeroSumSublists(ListNode* head) {if(head == NULL)return NULL;ListNode *newHead = new ListNode(0);//為方便處理添加哨兵，值為0newHead->next = head;ListNode *prev = newHead, *cur = head, *temp;unordered_map<int,ListNode*> m;m[0] = prev;//哨兵添加進哈希表int sum = 0, s;unordered_map<int,ListNode*>::iterator it;while(cur != NULL){sum += cur->val;it = m.find(sum);if(it == m.end())m[sum] = cur;else//找到了一樣的值{temp = it->second->next;s = it->first + temp->val;while(s != sum)//清空待刪除段的哈希表{m.erase(s);temp = temp->next;s += temp->val;}it->second->next = cur->next;//斷開中間的sum為0鏈表段sum = it->first;//sum重置為刪除段前面的}cur = cur->next;}ListNode *ans = newHead->next;delete newHead;//釋放哨兵return ans;} };

總結

以上是生活随笔為你收集整理的LeetCode 1171. 从链表中删去总和值为零的连续节点（哈希表）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。