Daily question 1: delete continuous nodes with a total value of zero from the linked list

1171. Delete consecutive nodes with zero sum from the linked list

Medium difficulty

Give you a list of the head node head, Please write code , Delete from the linked list repeatedly The sum of the The value is 0 Of Continuous node The sequence of components , Until there is no such sequence .

After deleting , Please return the head node of the final result linked list .

You can return any answer that meets the requirements of the question .

（ Be careful , All sequences in the following example , All right. ListNode Representation of object serialization .）

Example 1：

 Input ：head = [1,2,-3,3,1]
 Output ：[3,1]
 Tips ： answer  [1,2,1]  It's also true .

Example 2：

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

Example 3：

 Input ：head = [1,2,3,-3,-2]
 Output ：[1]

---

Violence solution ：

​ If you want to traverse to each group, the sum is equal to 0 Continuous node of , You can start from each node , Traverse its suffix and , If its suffix sum equals 0 了 , Specify the starting node of the current traversal to make the suffix sum equal to 0 These nodes of are a set of summation equals 0 Continuous node of , Should be deleted , But don't delete, Because after testing, if delete After the U-turn node Leetcode Will report a mistake , Guess it might be related to Leetcode The implementation of the linked list of test cases is related , So the way to delete it is cur->next = search->next, here cur Is the previous node of the starting node ,search Is to make the prefix and equal 0 The node of .

​ In order to avoid the difficulty of returning to a new head node after the head node is deleted , At the same time, it can be matched with the idea of the previous node of the starting node , You can add a sentinel node newhead.

Code ：

/** * 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) {
    
        // Create a head node 
        ListNode* newhead = new ListNode(0, head);
        
        // Create a cur Used as the starting node of each traversal 
        ListNode* cur = newhead;
        while(cur != nullptr)
        {
    
            int sum = 0;
            ListNode* search = cur->next;
            while(search != nullptr)
            {
    
                sum += search->val;
                if(sum == 0)
                {
    
                    cur->next = search->next;
                }
                search = search->next;
            }
            cur = cur->next;
        }

        ListNode* tmp = newhead->next;
        delete newhead;
        return tmp;
    }
};