Leetcode 1171. Remove Zero Sum Consecutive Nodes from Linked List

Problem statement

https://leetcode.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list/

Solution

We need to transform given linked list to usual list, then use cumulative sums to remove elements, then transform back.

Complexity

It is O(n^2) for time and O(n) for space.

Code

class Solution:
    def removeZeroSumSublists(self, head):
        arr = []
        while head:
            arr += [head.val]
            head = head.next
            
        for i in range(len(arr)):
            d = {0:-1}
            for i, val in enumerate(accumulate(arr)):
                if val in d:
                    arr = arr[:d[val] + 1] + arr[i+1:]
                    break
                d[val] = i
            
        head = curr = ListNode(-1)
        for x in arr:
            curr.next = ListNode(x)
            curr = curr.next
            
        return head.next