2023.6.11 从链表中删去总和值为0的节点-526互联

对一个序列进行前缀和处理，假设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
    }
}