How to Remove Zero Sum Consecutive Nodes from Linked List using

  • 时间:2020-09-10 13:03:17
  • 分类:网络文摘
  • 阅读:86 次

Given the head of a linked list, we repeatedly delete consecutive sequences of nodes that sum to 0 until there are no such sequences. After doing so, return the head of the final linked list. You may return any such answer.

(Note that in the examples below, all sequences are serializations of ListNode objects.)

Example 1:
Input: head = [1,2,-3,3,1]
Output: [3,1]
Note: The answer [1,2,1] would also be accepted.

Example 2:
Input: head = [1,2,3,-3,4]
Output: [1,2,4]

Example 3:
Input: head = [1,2,3,-3,-2]
Output: [1]

Constraints:
The given linked list will contain between 1 and 1000 nodes.
Each node in the linked list has -1000 <= node.val <= 1000.

Hints:
Convert the linked list into an array.
While you can find a non-empty subarray with sum = 0, erase it.
Convert the array into a linked list.

Remove Zero-Sum Link Node usig Prefix/Cumulative Sum

The prefix sum can be stored and retrieved using a hash map. We accumulate the sum (as key), and store its node as value in the hash map. Then, when a sum occurs, we know the interval between two link nodes sum to zero. We can then re-point the previous node’s next to the next node which effectively removes the nodes between.

At the meantime, if the Cumulative sum from the begining is zero, we need to reset the head and recursively remove the zero sum lists.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeZeroSumSublists(ListNode* head) {
        ListNode* newHead = head;
        unordered_map<int, ListNode*> prefix;
        int sum = 0;
        bool flag = false;        
        while (head) {
            sum += head->val;
            if (sum == 0) {
                newHead = head->next;
                flag = true;
                break;
            } else if (prefix.find(sum) == prefix.end()) {
                prefix[sum] = head;
            } else {
                prefix[sum]->next = head->next;
                flag = true;
            }
            head = head->next;
        }
        if (flag) {
            return removeZeroSumSublists(newHead);
        }
        return newHead;
    }
};
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeZeroSumSublists(ListNode* head) {
        ListNode* newHead = head;
        unordered_map<int, ListNode*> prefix;
        int sum = 0;
        bool flag = false;        
        while (head) {
            sum += head->val;
            if (sum == 0) {
                newHead = head->next;
                flag = true;
                break;
            } else if (prefix.find(sum) == prefix.end()) {
                prefix[sum] = head;
            } else {
                prefix[sum]->next = head->next;
                flag = true;
            }
            head = head->next;
        }
        if (flag) {
            return removeZeroSumSublists(newHead);
        }
        return newHead;
    }
};

The above C++ code to remove the zero sum nodes for a given linked list runs at O(N) time and require O(N) space – using a hash map.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
闹钟拨快了多少怎么算?  循环小数如何化成分数  圣经数  他是怎样猜出哪里手里的金币是单数的?  这本书共有多少页?  他们的职业各是什么?  你知道他们的名次吗?  关于逻辑推理的故事  求一个数是另一个数的几分之几,为什么要用第一个数除以第二个数?  这筐苹果至少有多少个? 
评论列表
添加评论