Skip to content

1171. Remove Zero Sum Consecutive Nodes from Linked List 👍

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  ListNode* removeZeroSumSublists(ListNode* head) {
    ListNode dummy(0, head);
    int prefix = 0;
    unordered_map<int, ListNode*> prefixToNode;
    prefixToNode[0] = &dummy;

    for (; head; head = head->next) {
      prefix += head->val;
      prefixToNode[prefix] = head;
    }

    prefix = 0;

    for (head = &dummy; head; head = head->next) {
      prefix += head->val;
      head->next = prefixToNode[prefix]->next;
    }

    return dummy.next;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public ListNode removeZeroSumSublists(ListNode head) {
    ListNode dummy = new ListNode(0, head);
    int prefix = 0;
    Map<Integer, ListNode> prefixToNode = new HashMap<>();
    prefixToNode.put(0, dummy);

    for (; head != null; head = head.next) {
      prefix += head.val;
      prefixToNode.put(prefix, head);
    }

    prefix = 0;

    for (head = dummy; head != null; head = head.next) {
      prefix += head.val;
      head.next = prefixToNode.get(prefix).next;
    }

    return dummy.next;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
  def removeZeroSumSublists(self, head: ListNode) -> ListNode:
    dummy = ListNode(0, head)
    prefix = 0
    prefixToNode = {0: dummy}

    while head:
      prefix += head.val
      prefixToNode[prefix] = head
      head = head.next

    prefix = 0
    head = dummy

    while head:
      prefix += head.val
      head.next = prefixToNode[prefix].next
      head = head.next

    return dummy.next