【每日一题Day234】LC1171从链表中删去总和值为零的连续节点 | 链表模拟 哈希表+前缀和

简介: 【每日一题Day234】LC1171从链表中删去总和值为零的连续节点 | 链表模拟 哈希表+前缀和

从链表中删去总和值为零的连续节点【LC1171】

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

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

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

(注意,下面示例中的所有序列,都是对 ListNode对象序列化的表示。)

周赛三题选手,努力提升速度

链表模拟
  • 思路:
    对于每个节点cur,判断以其为首的连续节点之和是否为0,如果存在那么将其的前置节点指向其的下一个节点,直至链表中所有节点都判断完
  • 迭代实现
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
        // 对于每个节点,判断以其为首的连续节点之和是否为0,如果存在那么将其的pre指向其下一个节点
        // 最坏每个节点都不存在O(n^2)
        ListNode dummy = new ListNode(-1, head);
        ListNode pre = dummy;
        while (pre.next != null){
            int sum = 0;
            boolean del = false;
            for (ListNode cur = pre.next; cur != null; cur = cur.next){
                sum += cur.val;
                if (sum == 0){
                    pre.next = cur.next;
                    del = true;
                    break;
                }
            }                        
            if (!del){
                pre = pre.next;
            }      
        }
        return dummy.next;
    }
}

image.png

 class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
        //方法一、 直接递归
        if(head == null) return null;
        int sum = 0;
        for(ListNode p = head; p != null; p = p.next)
        {
            sum += p.val;
            if(sum == 0) return removeZeroSumSublists(p.next);
        }
        head.next = removeZeroSumSublists(head.next);
        return head;
    }
}

image.png

前缀和+哈希表
  • 思路如果链表中的两个节点的前缀和相等,那么可以将该段链表删除
  • 因此可以先遍历一边链表使用哈希表记录前缀和以及对应的链表节点,相同的前缀和记录出现的最后一个节点
  • 再遍历一边链表,如果某个节点对应的前缀和在哈希表中出现过,那么将该段链表删除
  • 实现
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        Map<Integer, ListNode> last = new HashMap<>();
        int s = 0;
        ListNode cur = dummy;
        while (cur != null) {
            s += cur.val;
            last.put(s, cur);
            cur = cur.next;
        }
        s = 0;
        cur = dummy;
        while (cur != null) {
            s += cur.val;
            cur.next = last.get(s).next;
            cur = cur.next;
        }
        return dummy.next;
    }
}
作者:ylb
链接:https://leetcode.cn/problems/remove-zero-sum-consecutive-nodes-from-linked-list/solutions/2304678/python3javacgotypescript-yi-ti-yi-jie-qi-3vsy/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

image.png


目录
相关文章
|
2月前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
25 0
LeetCode第二十四题(两两交换链表中的节点)
|
2月前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
45 0
Leetcode第十九题(删除链表的倒数第N个节点)
05_删除链表的倒数第N个节点
05_删除链表的倒数第N个节点
|
2月前
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
56 0
|
4月前
|
算法
LeetCode第24题两两交换链表中的节点
这篇文章介绍了LeetCode第24题"两两交换链表中的节点"的解题方法,通过使用虚拟节点和前驱节点技巧,实现了链表中相邻节点的交换。
LeetCode第24题两两交换链表中的节点
04_两两交换链表中的节点
04_两两交换链表中的节点
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
Leetcode题目"剑指 Offer 22. 链表中倒数第k个节点"的Python解决方案,使用双指针法找到并返回链表中倒数第k个节点。
57 5
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 18. 删除链表的节点
Leetcode题目"剑指 Offer 18. 删除链表的节点"的Python解决方案,通过使用双指针法找到并删除链表中值为特定数值的节点,然后返回更新后的链表头节点。
46 4
|
5月前
|
安全 云计算
云计算自旋锁问题之在线程安全地删除链表节点时,需要频繁加锁会影响性能如何解决
云计算自旋锁问题之在线程安全地删除链表节点时,需要频繁加锁会影响性能如何解决
55 2
|
6月前
|
算法
【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)
【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)