Library Ledger Voids

Linked list after repeatedly removing earliest-start, longest zero-sum blocks

MediumLinked ListPrefix SumsHash Table

A library records account adjustments in a singly linked ledger. Each node contains a signed integer: a charge is positive, a credit is negative, and a bookkeeping entry may be zero.

A voidable block is a nonempty consecutive sequence of nodes whose values sum to zero. The library cleans the ledger using this exact procedure:

  1. Scan the current ledger from its head and find the first node that starts any voidable block.
  2. If several voidable blocks start at that node, remove the longest one.
  3. Restart the scan from the head of the remaining ledger.
  4. Stop when no voidable block remains.

Given head, return the head of the final ledger. Return an empty list if every entry is removed.

Implement the cleanup by changing links between existing nodes, rather than copying their values into a replacement list. The returned nodes must keep their original relative order.

Examples

Example 1

Input: head = [3,-1,-2,4,-4,7]
Output: [7]

At the first entry, both the initial three entries and the initial five entries sum to zero. The longer block is removed, leaving only the final entry.

Example 2

Input: head = [5,2,-2,3,-3,8]
Output: [5,8]

The first entry cannot start a zero-sum block. The block beginning at the second entry has two possible zero-sum endings; the later ending is chosen. The first and last entries remain.

Example 3

Input: head = [1,2,4]
Output: [1,2,4]

All entries are positive, so no nonempty block can be voided. The ledger remains unchanged.

Constraints

  • The linked list contains between 0 and 10,000 nodes.
  • Each node value is an integer between -1,000 and 1,000.
  • The input list is acyclic.

The intended complexity is O(n) expected time and O(n) auxiliary space. The cleanup order is part of the specification and makes the result unique. TreeNode and ListNode classes are supplied by the platform.

Hints

Show hint 1

Two equal prefix sums mark a consecutive block with sum zero. Include a prefix sum of zero before the head.

Show hint 2

For each prefix sum, remember its last node in the original ledger. A second traversal can bypass the longest removable block after each retained prefix.

Follow-up questions

What an interviewer might ask once you have a working solution.

  • Explain why bypassing blocks using the original prefix sums produces exactly the specified repeated-cleanup result.
  • Can you preserve the original list and build a separate result instead? Describe the additional space required.

Practice this with an AI interviewer

Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.

Start this problem