对一个序列进行前缀和处理,假设p处前缀和与q处前缀和相等,说明\((p, q)\)之间的序列和为0。
因此我们可以遍历一次链表,预处理出前缀和,同时用哈希表记录,哈希表的key为前缀和,value为所处节点。遇到相同的key时,直接覆盖,这样哈希表存储的就是前缀和为key的最后一个节点。
第二次遍历链表,根据当前节点的前缀和,查找哈希表中存储的具有相同前缀和的最后一个节点,两个节点之间的连续和为0,因此直接删去。重复该操作,就可以得到答案。
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
use std::collections::HashMap;
impl Solution {
pub fn remove_zero_sum_sublists(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
if head.is_none() { return head; }
let mut dummy = Box::new(ListNode::new(0));
dummy.next = head; // 此处发生移动,head的所有权已经被移动至dummy
let mut map = HashMap::new();
let mut sum = 0;
let mut p = dummy.next.as_ref(); // p是可改变引用对象的不可变引用
map.insert(0, dummy.as_ref());
while let Some(_p) = p
{
sum += _p.val;
p = _p.next.as_ref();
map.insert(sum, _p.as_ref());
}
// 不能使用dummy,因为dummy已经有了不可变引用(HashMap中),就不能再创建它的可变引用
let mut ans = Box::new(ListNode::new(0));
let mut p = Some(&mut ans); // p是可改变引用对象的可变引用
sum = 0;
while let Some(_p) = p
{
sum += _p.val;
if let Some(q) = map.get(&sum)
{
_p.next = match q.next.as_ref() {
Some(next) => Some(Box::new(ListNode::new(next.val))),
None => None,
}
}
p = _p.next.as_mut();
}
ans.next
}
}
标签:11,mut,dummy,sum,值为,next,链表,let,new
From: https://www.cnblogs.com/st0rmKR/p/17472808.html