题目介绍
力扣1171题:leetcode-cn.com/problems/re…
分析
根据题目的意思,我们需要找到相加和为零并且连续的节点,有了这个条件,我们可以遍历一次链表,依次将每个节点的值相加,如果出现节点和一样的节点,那么说明在这些节点之间的节点值之和一定为零。
例如:对于head = [1,2,-3,3,1]
来说,遍历一次之后的节点之和sum的值为:[1,3,0,3,4]
,我们发现出现了两个3
,那就说明这两个节点之间的节点值之和为零,我们只需要将这部分节点删除即可。
有了上面的思路之后,我们可以使用HashMap数据结构,对于节点值和一样的节点,HashMap会将之前进行覆盖。刚好可以利用HashMap这个特点删除节点值之和为零的连续节点。
代码如下:
/**
* 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> map = new HashMap<>();
// 首次遍历建立 节点处链表和<->节点 哈希表
// 若同一和出现多次会覆盖,即记录该sum出现的最后一次节点
int sum = 0;
for (ListNode d = dummy; d != null; d = d.next) {
sum += d.val;
map.put(sum, d);
}
// 第二遍遍历 若当前节点处sum在下一处出现了则表明两结点之间所有节点和为0 直接删除区间所有节点
sum = 0;
for (ListNode d = dummy; d != null; d = d.next) {
sum += d.val;
d.next = map.get(sum).next;
}
return dummy.next;
}
}
复制代码
近期评论