{"id":5495,"date":"2019-08-24T23:25:34","date_gmt":"2019-08-25T06:25:34","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5495"},"modified":"2020-10-04T10:10:03","modified_gmt":"2020-10-04T17:10:03","slug":"leetcode-1171-remove-zero-sum-consecutive-nodes-from-linked-list","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/list\/leetcode-1171-remove-zero-sum-consecutive-nodes-from-linked-list\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1171. Remove Zero Sum Consecutive Nodes from Linked List"},"content":{"rendered":"\n<p>Given the&nbsp;<code>head<\/code>&nbsp;of a linked list, we repeatedly delete consecutive sequences of nodes that sum to&nbsp;<code>0<\/code>until there are no such sequences.<\/p>\n\n\n\n<p>After doing so, return the head of the final linked list.&nbsp; You may return any such answer.<\/p>\n\n\n\n<p>(Note that in the examples below, all sequences are serializations of&nbsp;<code>ListNode<\/code>&nbsp;objects.)<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> head = [1,2,-3,3,1]\n<strong>Output:<\/strong> [3,1]\n<strong>Note:<\/strong> The answer [1,2,1] would also be accepted.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> head = [1,2,3,-3,4]\n<strong>Output:<\/strong> [1,2,4]\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> head = [1,2,3,-3,-2]\n<strong>Output:<\/strong> [1]\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>The given linked list will contain between&nbsp;<code>1<\/code>&nbsp;and&nbsp;<code>1000<\/code>&nbsp;nodes.<\/li><li>Each node in the linked list has&nbsp;<code>-1000 &lt;= node.val &lt;= 1000<\/code>.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: HashTable<\/strong><\/h2>\n\n\n\n<p>Similar to target sum = 0, use a hashtable to store the first ListNode* that has a given prefix sum. Whenever the same prefix sum occurs, skip all the elements between the first occurrence and current one, e.g. first_sum_x.next = curr_sum_x.next<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  ListNode* removeZeroSumSublists(ListNode* head) {\n    bool done = false;\n    function<ListNode*(ListNode*)> helper = [&](ListNode* head) {\n      ListNode dummy(0);\n      dummy.next = head;    \n      ListNode* prev = &dummy;\n      ListNode* curr = prev->next;\n      unordered_map<int, ListNode*> m{{0, prev}};    \n      int s = 0;\n      done = true;\n      while (curr) {\n        s += curr->val;      \n        if (m.count(s)) {\n          m[s]->next = curr->next;\n          done = false;\n        } else {\n          m[s] = curr;\n        }\n        prev = curr;\n        curr = curr->next;\n      }\n      return dummy.next;\n    };\n    while (!done) head = helper(head);\n    return head;\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\n# Author: Huahua\nclass Solution:\n  def removeZeroSumSublists(self, head: ListNode) -> ListNode:\n    def helper(head: ListNode):      \n      dummy = ListNode(0)\n      dummy.next = head\n      prev, curr = dummy, dummy.next    \n      s = 0\n      m = {s: prev}\n      done = True\n      while curr:\n        s += curr.val\n        if s in m:\n          m[s].next = curr.next\n          done = False\n        else:\n          m[s] = curr\n        prev, curr = curr, curr.next\n      return dummy.next, done\n    while True:\n      head, done = helper(head)\n      if done: return head\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given the&nbsp;head&nbsp;of a linked list, we repeatedly delete consecutive sequences of nodes that sum to&nbsp;0until there are no such sequences. After doing so, return the&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[50],"tags":[82,83,177,492],"class_list":["post-5495","post","type-post","status-publish","format-standard","hentry","category-list","tag-hashtable","tag-list","tag-medium","tag-target-sum","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5495","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=5495"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5495\/revisions"}],"predecessor-version":[{"id":7455,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5495\/revisions\/7455"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5495"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5495"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5495"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}