2023-06-11 LeetCode每日一题（从链表中删去总和值为零的连续节点）网站首页 技术教程

2023-06-11 LeetCode每日一题（从链表中删去总和值为零的连续节点）

HEU_firejef 2024-10-08 00:01:03

简介2023-06-11 LeetCode每日一题（从链表中删去总和值为零的连续节点）

2023-03-29每日一题

一、题目编号

1171. 从链表中删去总和值为零的连续节点

二、题目链接

点击跳转到题目位置

三、题目描述

给你一个链表的头节点 head，请你编写代码，反复删去链表中由总和值为 0 的连续节点组成的序列，直到不存在这样的序列为止。

删除完毕后，请你返回最终结果链表的头节点。

你可以返回任何满足题目要求的答案。

提示：

给你的链表中可能有 1 到 1000 个节点。
对于链表中的每个节点，节点的值：-1000 <= node.val <= 1000.

四、解题代码

/**
 * 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) {
        vector<int> nums;
        while(head != nullptr){
            nums.push_back(head->val);
            head = head->next;
        }
        while(1){
            unordered_map<int, int> hash;
            int flag1 = 0;
            vector<int> res;
            int num = 0;
            int n = nums.size();
            for(int i = 0; i < n; ++i){
                num += nums[i];
                res.push_back(nums[i]);
                if(hash[num] != 0 || num == 0){
                    flag1 = 1;
                    int index = num;
                    res.pop_back();
                    num -= nums[i];
                    int j = res.size()-1;
                    while(num != index){
                        hash[num] = 0;
                        num -= res[j];
                        --j;
                        res.pop_back();
                    }
                    hash[num] = 0;
                continue;
                }
                hash[num] = 1;
            }
            nums = res;
            if(flag1 == 0){
                break;
            }
        }
        ListNode* Dummyhead = new ListNode();
        ListNode* Head = Dummyhead;
        int n = nums.size();
        for(int i = 0; i < n; ++i){
            ListNode *node = new ListNode(nums[i]);
            Head->next = node;
            Head = Head->next;
        }
    return Dummyhead->next;
    }
};