您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

【Leetcode】1171. Remove Zero Sum Consecutive Nodes from Linked List

题目地址:

https://leetcode.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list/

给定一个链表,要求删去其所有和为 0 0 0的连续子段,使得结果中不含和为 0 0 0的子段。答案不唯一,合法即可。

思路是用哈希表。先求一下前缀和,边求边存储该前缀和所对应的最后一个节点是谁。接着再遍历一遍链表,同时再计算前缀和,这时如果当前节点不是该前缀和所对应的最后一个节点时候,就可以将中间这一段直接删去(因为中间这一段和必为 0 0 0)。所剩的链表里必然不存在和为 0 0 0的子段,否则算法走到这一段的前一个节点的时候必然会将其删去,就矛盾了。代码如下:

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        int sum = 0;
        Map<Integer, ListNode> map = new HashMap<>();
        map.put(0, dummy);
        for (ListNode cur = dummy; cur != null; cur = cur.next) {
            sum += cur.val;
            map.put(sum, cur);
        }
        
        sum = 0;
        for (ListNode cur = dummy; cur != null; cur = cur.next) {
            sum += cur.val;
            // 如果cur不是sum对应的最后一个节点的话,这一句将会将中间和为0的一段删去
            cur.next = map.get(sum).next;
        }
        
        return dummy.next;
    }
}

class ListNode {
    int val;
    ListNode next;
    
    public ListNode(int val) {
        this.val = val;
    }
}

时空复杂度 O ( n ) O(n) O(n) n n n是链表长度。


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进