每日一题：从链表中删去总和值为零的连续节点

利刃大大

发布于 2023-04-12 14:07:36

9860

发布于 2023-04-12 14:07:36

文章被收录于专栏：编程语言/linux/算法

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

难度中等

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

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

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

（注意，下面示例中的所有序列，都是对 ListNode 对象序列化的表示。）

示例 1：

输入：head = [1,2,-3,3,1]
输出：[3,1]
提示：答案 [1,2,1] 也是正确的。

示例 2：

输入：head = [1,2,3,-3,4]
输出：[1,2,4]

示例 3：

输入：head = [1,2,3,-3,-2]
输出：[1]

暴力解法：

如果要遍历到每一组求和等于0的连续结点，可以从每个结点出发，遍历它的后缀和，如果它的后缀和等于0了，说明当前遍历的起始结点到令后缀和等于0的这些结点是一组求和等于0的连续结点，应当删除掉，但是不要delete,因为经过测试如果delete掉头结点后 Leetcode会报错，猜测可能和 Leetcode 的测试用例的链表实现有关系，所以删除掉的方法就是cur->next = search->next,这里cur是起始结点的前一个结点，search是使前缀和等于0的结点。

为了避免头结点删除后返回新的头结点的困难，同时可以和起始结点的前一个结点这一想法相配合，可以增加一个哨兵结点 newhead.

代码：

/**
 * 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* newhead = new ListNode(0, head);
        
        //创建一个cur用来作为每次遍历的起始节点
        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;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-07-24，如有侵权请联系 cloudcommunity@tencent.com 删除

遍历