Leetcode Problem 1171. Remove Zero Sum Consecutive Nodes from Linked List

1171. Remove Zero Sum Consecutive Nodes from Linked List

Leetcode Solutions

Using Prefix Sum and HashMap

  1. Create a dummy node with value 0 and point its next to head.
  2. Initialize a hashmap to store prefix sum and corresponding node.
  3. Initialize prefix sum to 0.
  4. Traverse the linked list from the dummy node. a. Update the prefix sum by adding the current node's value. b. Check if the prefix sum is in the hashmap. i. If it is, it means we found a zero-sum sublist. Set the next of the node in hashmap to current node's next. ii. Remove all prefix sums from the hashmap that are part of the zero-sum sublist. c. If the prefix sum is not in the hashmap, add it with the current node.
  5. Move to the next node and repeat steps 4a to 4c.
  6. Return the next of the dummy node, which is the head of the modified list.
UML Thumbnail

Recursive Approach

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...