c++ - 从链接列表中删除零个连续的求和节点-此代码如何用于这样的测试用例？

Question

我有一个这样的链接列表作为我的输入(1) -> (2) -> (3) -> (-3) -> (4) -> NULL我希望删除总和等于零的连续节点，即我希望我的输出链接列表像这样:(1) -> (2) -> (4) -> NULL
我已经使用map和array的方法解决了这个问题，然后遇到了下面显示的代码。对于上面的测试用例，此代码可以很好地工作，我无法理解该怎么做？

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
    ListNode* removeZeroSumSublists(ListNode* head) {
        ListNode* new_head = new ListNode(0);
        new_head->next = head;
        ListNode* cur = new_head;
        while(cur != NULL)
        {
            int sum=0;
            while(head != NULL)
            {
                sum += head->val;
                if(sum == 0)
                {
                   cur->next = head->next; 
                }
                head = head->next;
            }
            //What is happening here???
            cur = cur->next;
            if(cur != NULL)
            {
                head = cur->next;
            }
        }
        return new_head->next; 
    }
};

有人可以给我一个解释吗？

Answer 1

(cur)从列表的开头进行迭代。
对于每个(cur)开始对(cur)之后的元素求和。
当sum=0更新(cur)->next指向此和之后的第一个元素时。因此，跳过(cur)后带有sum=0的前K个元素。
循环执行此操作，直到列表结尾。在每个循环迭代中，将跳过带有sum=0的前K个元素。

// the first K elements starting after (cur) with sum=0 are skipped,
//so (cur) now points to K+1.th element.
            cur = cur->next;
            if(cur != NULL)
            {
                head = cur->next;
            }

时间复杂度为 O(N*N)。