首页 > 其他分享 >leetcode 1171. 从链表中删去总和值为零的连续节点

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

时间:2023-06-11 19:32:02浏览次数:37  
标签:node ListNode val 1171 值为 next 链表 节点

给你一个链表的头节点 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]

提示:

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

建立哈希表,key为节点值的前缀和,value为节点。

第一次循环遍历,累加前缀和,并逐一写入哈希表,重复的值会自动替换为最新的。

第二次遍历,让节点指向存在哈希表中当前前缀和的节点,中间跳过的部分总和即为 leetcode 1171. 从链表中删去总和值为零的连续节点_链表

/**
 * 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);
        dummy.next=head;
        Map<Integer,ListNode>seen=new HashMap<>();
        int prefix=0;
        for(ListNode node=dummy;node!=null;node=node.next){
            prefix+=node.val;
            seen.put(prefix,node);

        }

        prefix=0;
        for(ListNode node=dummy;node!=null;node=node.next){
            prefix+=node.val;
            node.next=seen.get(prefix).next;

        }
        return dummy.next;
    }
}

标签:node,ListNode,val,1171,值为,next,链表,节点
From: https://blog.51cto.com/u_15983387/6458696

相关文章

  • Leetcode 1171. 从链表中删去总和值为零的连续节点
    题目:给你一个链表的头节点 head,请你编写代码,反复删去链表中由总和 值为0的连续节点组成的序列,直到不存在这样的序列为止。删除完毕后,请你返回最终结果链表的头节点。你可以返回任何满足题目要求的答案。(注意,下面示例中的所有序列,都是对 ListNode 对象序列化的表示。)难......
  • 根据已有链表中的元素进行排序
    思想为先将链表中的每一个节点映射到一个链表节点为变量的数组里,在根据节点的元素进行排序,本程序为ave,过程中将数组变量排序,最后重新生成链voidpaixu(LinkListhead)//从大到小{intlength=len(head),i=0,j=0,sum1[length],n1;LinkListsum[length];LinkListpa=hea......
  • 第四天打卡|24. 两两交换链表中的节点 ● 19.删除链表的倒数第N个节点 面试题 02.07.
    24.两两交换链表中的节点:简单的交换 19.删除链表的倒数第N个节点: ●  面试题 02.07. 链表相交:这题没看过答案真的写不出来。太巧妙了  142.环形链表II:这题写过但是忘记怎么解的了还是看的答案。下次不能忘记  ......
  • 2023.6.11 从链表中删去总和值为0的节点
    对一个序列进行前缀和处理,假设p处前缀和与q处前缀和相等,说明\((p,q)\)之间的序列和为0。因此我们可以遍历一次链表,预处理出前缀和,同时用哈希表记录,哈希表的key为前缀和,value为所处节点。遇到相同的key时,直接覆盖,这样哈希表存储的就是前缀和为key的最后一个节点。第二次遍历......
  • #yyds干货盘点# LeetCode程序员面试金典:环形链表
    题目:给你一个链表的头节点head,判断链表中是否有环。如果链表中有某个节点,可以通过连续跟踪next指针再次到达,则链表中存在环。为了表示给定链表中的环,评测系统内部使用整数pos来表示链表尾连接到链表中的位置(索引从0开始)。注意:pos不作为参数进行传递 。仅仅是为了标识链......
  • #yyds干货盘点# LeetCode程序员面试金典:移除链表元素
    1.简述:给你一个链表的头节点head和一个整数val,请你删除链表中所有满足Node.val==val的节点,并返回新的头节点。 示例1:输入:head=[1,2,6,3,4,5,6],val=6输出:[1,2,3,4,5]示例2:输入:head=[],val=1输出:[]示例3:输入:head=[7,7,7,7],val=7输出:[]2.代码实现:class......
  • 《数据结构与算法》之队列与链表复习
    导言:我们在上一次学习了堆栈的数据结构以后,可以了解到它是受限制的操作,比如我们操作只能在栈顶,现在我们要学习的东西叫做队列,它也是受限制的一种数据结构,它的特点是队头只出数据,而队尾只入数据,它的结构就和它的名字,像我们平时排队一样先来的人肯定要先服务啊,所以它的英文叫做Fri......
  • 13.双向链表的算法实现
      单链表中每个结点除了存储自身数据之后,还存储了下一个结点的地址,因此可以轻松访问下一个结点,以及后面的后继结点,但是如果想访问前面的结点就不行了,再也回不去了。  例如删除结点p时,要先找到它的前一个结点q,然后才能删掉p结点,单向链表只能往后走,不能向前走。如果需要向前走......
  • 反转链表
    头插法:classSolution{publicListNodereverseList(ListNodehead){ListNodenewHead=newListNode(0);newHead.next=null;ListNodep=head;ListNodeq;while(p!=null){q=p;p=p.next;......
  • 代码随想录算法训练营第四天|24. 两两交换链表中的节点 , 19.删除链表的倒数第N个节点
    24.两两交换链表中的节点 个人感觉这个不太难,刚开始打算用步进值为2,来搞,但是没有想到链表应该是怎么样的,原来可以直接用: 1cur=cur->next->next 学到了,这是我自己写的代码:1ListNode*MyLinkedList::swapPairs(ListNode*head)2{3ListNode*dummyHead=new......