Cancel Zero-Sum Stretches

Medium

You are given a singly linked list of integers head. A stretch is one or more consecutive nodes. While the list contains a stretch that sums to 0, delete one according to this rule: - among all zero-sum stretches, take the one that starts furthest to the left; - if there are several, take the longest. Once no zero-sum stretch is left, return the head of the resulting list (which may be empty).

Example 1

head=list_node([4, 2, -6, 5, 1]) → [5, 1]

The leftmost zero-sum stretch is 4, 2, -6. Removing it leaves [5, 1], which has no zero-sum stretches.

Example 2

head=list_node([3, 1, -1, 2, -2, 7]) → [3, 7]

The leftmost zero-sum stretch starts at 1, and the longest one from there is 1, -1, 2, -2. What remains is [3, 7].

Example 3

head=list_node([5, -5, 0]) → None

The whole list sums to 0 and is removed entirely, so the answer is empty.

Constraints

The list has between 1 and 10⁴ nodes
-1000 ≤ Node.val ≤ 1000

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Hash Table Linked List

Similar problems

Marked Runs in a Chain Medium Keep Only One-Off Values in a List Medium Purge Banned Values Medium How Often Each Value Appears Easy Adding Digit Lists Medium

Input

head=list_node([4, 2, -6, 5, 1])

Expected

[5, 1]

Run checks the first 3 tests in your browser. Submit checks all 121 tests on the server, hidden ones included.