Remove zero sum consecutive nodes from linked list

Hash Table Linked List

53.1% acceptance

Feb 25, 2026

3502

226

Given the head of a linked list, we repeatedly delete consecutive sequences of nodes that sum to 0 until there are no such sequences. After doing so, return the head of the final linked list. You may return any such answer. (Note that in the examples below, all sequences are serializations of ListNode objects.)

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

impl Solution {
  pub fn remove_zero_sum_sublists(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    // Convert to vec, process, rebuild
    let mut vals = Vec::new();
    let mut cur = head.as_ref();
    while let Some(node) = cur {
      vals.push(node.val);
      cur = node.next.as_ref();
    }
    // Remove zero-sum subsequences
    loop {
      let mut prefix_map: HashMap<i32, usize> = HashMap::new();
      let mut prefix = 0;
      let mut removed = false;
      prefix_map.insert(0, usize::MAX); // sentinel
      let mut i = 0;
      while i < vals.len() {
        prefix += vals[i];
        if let Some(&prev_i) = prefix_map.get(&prefix) {
          // Remove vals[prev_i+1..=i]
          let start = if prev_i == usize::MAX { 0 } else { prev_i + 1 };
          vals.drain(start..=i);
          removed = true;
          break;
        }
        prefix_map.insert(prefix, i);
        i += 1;
      }
      if !removed { break; }
    }
    // Rebuild linked list
    let mut head: Option<Box<ListNode>> = None;
    for &v in vals.iter().rev() {
      let mut node = Box::new(ListNode::new(v));
      node.next = head;
      head = Some(node);
    }
    head
  }
}