美文网首页算法
1171. 从链表中删去总和值为零的连续节点

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

作者: 红树_ | 来源:发表于2023-06-10 16:29 被阅读0次

LC每日一题,参考1171. 从链表中删去总和值为零的连续节点 - 力扣(Leetcode)

题目

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

删除完毕后,请你返回最终结果链表的头节点。你可以返回任何满足题目要求的答案。
(注意,下面示例中的所有序列,都是对 ListNode 对象序列化的表示。)

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

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

解题思路

  • 前缀和+哈希表:连续序列值为零,即前缀和某个区间为零,即某两个前缀和相等,可使用哈希表查找。

前缀和+哈希表

class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
        //前缀和+哈希 (和为零即当前前缀和是否已经存在)
        int[] presum = new int[1001];
        int i = 0;
        HashMap<Integer,ListNode> map = new HashMap<>();
        ListNode dummy = new ListNode(0,head);
        map.put(0,dummy);
        while(head != null) {
            presum[i+1] = presum[i] + head.val;
            ListNode node = map.get(presum[i+1]);
            if(node != null) {//删除节点区间(node,head]以及哈希
                int j = i;
                while(j >= 0 && presum[j] != presum[i+1]){
                    map.remove(presum[j--]);//map.put(presum[j--],null);
                }
                node.next = head.next;
            }else{//存储
                map.put(presum[i+1],head);
            }
            head = head.next;
            i++;
        }
        //[1,2,3,-3,-2] -> 0 1 3 6 3 1
        return dummy.next;
    }
}

复杂度分析

  • 时间复杂度:O(n)n为链表长度,遍历链表一次n,删除区间最多不超过n次。
  • 空间复杂度:O(n),前缀和数组n,哈希表空间不超过n

相关文章

  • 手撕LeetCode #1171——Python

    1171. 从链表中删去总和值为零的连续结点[https://leetcode-cn.com/problems/r...

  • leetcode链表之从链表中删除总和值为零的连续结点

    1171、从链表中删除总和值为零的连续结点[https://leetcode-cn.com/problems/re...

  • 第四次周测

    /*有两个链表a和b,设节点中包含学号、成绩。 从a链表中删去b链表中有相同学号的那些节点。 输入第一行有两个用空...

  • c语言插入删除链表

    1.题目描述 输入一个单向链表和一个节点的值,从单向链表中删除等于该值的节点,删除后如果链表中无节点则返回空指针。...

  • 剑指offer面试题05----从头到尾打印链表

    题目:输入一个链表,从尾到头打印链表每个节点的值。若列表为空,输出[ ]。 思考:面试中链表相关的题目有很多,这个...

  • 链表

    三种常见的链表结构: 1.单链表 2.双链表 3.循环链表 从链表中删除数据的2种情况: 1.删除节点中‘值为某个...

  • 面试题5:从尾到头打印链表

    题目描述 输入一个链表,从尾到头打印链表每个节点的值。 输入为链表的表头,输出为需要打印的“新链表”的表头。 代码...

  • [编程题]从尾到头打印链表

    输入一个链表,从尾到头打印链表每个节点的值。输入描述:输入为链表的表头输出描述:输出为需要打印的“新链表”的表头 ...

  • 1.单链表常用操作

    1.删除单链表中的指定节点 2.删除单链表中指定值的节点 (1). 利用栈删除单链表指定值的节点 (2). 用普通...

  • 2019-03-08 lintcode2

    二叉树路径遍历 输出所有根节点到叶子节点的路径找出所有路径中相加总和等于给定值的路径 数据结构 链表:遍历、增加、...

网友评论

    本文标题:1171. 从链表中删去总和值为零的连续节点

    本文链接:https://www.haomeiwen.com/subject/yovtydtx.html