Remove Zero Sum Consecutive Nodes from Linked List

Remove Zero Sum Consecutive Nodes from Linked List - Problem

Given the head of a linked list, we repeatedly delete consecutive sequences of nodes that sum to 0 until there are no such sequences.

After doing so, return the head of the final linked list. You may return any such answer.

Note that in the examples below, all sequences are serializations of ListNode objects.

Input & Output

Example 1 — Remove Middle Zero Sum

$ Input: head = [1,3,-3,2]

› Output: [1,2]

💡 Note: The consecutive nodes 3 and -3 sum to 0, so we remove them. The remaining list is [1,2].

Example 2 — Multiple Removals

$ Input: head = [1,2,-3,3,1]

› Output: [3,1]

💡 Note: First remove [1,2,-3] which sums to 0, leaving [3,1]. No more zero-sum sequences exist.

Example 3 — All Nodes Removed

$ Input: head = [1,2,3,-3,-2]

› Output: []

💡 Note: Remove [2,3,-3,-2] which sums to 0, leaving [1]. Then remove remaining [1] as it doesn't form zero sum alone.

Constraints

The number of nodes in the given linked list is in the range [1, 1000]
-1000 ≤ Node.val ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Linked list [1, 3, -3, 2] with consecutive 3, -3

Process

Find consecutive sequences that sum to 0

Output

Remove zero-sum sequences, return [1, 2]

Key Takeaway

🎯 Key Insight: Use prefix sums to detect when consecutive sequences sum to zero - repeated prefix sums indicate zero-sum ranges that can be removed efficiently.

Asked in

f Facebook 35 M Microsoft 25 G Google 20

The key insight is using prefix sums to detect zero-sum consecutive sequences efficiently. When the same prefix sum appears twice, the nodes between those positions sum to zero. Best approach uses hash map with O(n) time and O(n) space.

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map - Prefix Sum Optimization	O(n)	O(n)	Use prefix sums and hash map to efficiently detect zero-sum sequences
Brute Force - Check All Subsequences	O(n³)	O(1)	Check every possible consecutive subsequence for zero sum

Hash Map - Prefix Sum Optimization — Algorithm Steps

Step 1: Add dummy node and calculate prefix sums
Step 2: Store first occurrence of each prefix sum in hash map
Step 3: When prefix sum repeats, remove nodes between occurrences
Step 4: Continue until entire list is processed

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Prefix Sums

Running sum from start, store first occurrence

Detect Repeat

Same prefix sum means zero-sum sequence found

Remove Sequence

Delete nodes between repeated prefix sum positions

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

struct HashNode {
    int key;
    struct ListNode* node;
    struct HashNode* next;
};

#define HASH_SIZE 10007

struct HashNode* hashTable[HASH_SIZE];

int hash(int key) {
    return abs(key) % HASH_SIZE;
}

void insert(int key, struct ListNode* node) {
    int idx = hash(key);
    struct HashNode* newNode = malloc(sizeof(struct HashNode));
    newNode->key = key;
    newNode->node = node;
    newNode->next = hashTable[idx];
    hashTable[idx] = newNode;
}

struct ListNode* find(int key) {
    int idx = hash(key);
    struct HashNode* curr = hashTable[idx];
    while (curr) {
        if (curr->key == key) return curr->node;
        curr = curr->next;
    }
    return NULL;
}

void removeKey(int key) {
    int idx = hash(key);
    struct HashNode* curr = hashTable[idx];
    struct HashNode* prev = NULL;
    
    while (curr) {
        if (curr->key == key) {
            if (prev) prev->next = curr->next;
            else hashTable[idx] = curr->next;
            free(curr);
            return;
        }
        prev = curr;
        curr = curr->next;
    }
}

struct ListNode* createNode(int val) {
    struct ListNode* node = malloc(sizeof(struct ListNode));
    node->val = val;
    node->next = NULL;
    return node;
}

int* solution(int* head, int headSize, int* returnSize) {
    *returnSize = 0;
    if (headSize == 0) return NULL;
    
    // Initialize hash table
    for (int i = 0; i < HASH_SIZE; i++) {
        hashTable[i] = NULL;
    }
    
    // Convert array to linked list
    struct ListNode* dummy = createNode(0);
    struct ListNode* current = dummy;
    for (int i = 0; i < headSize; i++) {
        current->next = createNode(head[i]);
        current = current->next;
    }
    struct ListNode* listHead = dummy->next;
    
    struct ListNode* newDummy = createNode(0);
    newDummy->next = listHead;
    
    int prefixSum = 0;
    insert(0, newDummy);
    
    current = newDummy->next;
    
    while (current) {
        prefixSum += current->val;
        
        struct ListNode* start = find(prefixSum);
        if (start) {
            // Remove nodes between start and current
            struct ListNode* temp = start->next;
            
            // Remove the sum values from hash table
            int tempSum = prefixSum;
            while (temp != current) {
                tempSum += temp->val;
                removeKey(tempSum);
                temp = temp->next;
            }
            
            start->next = current->next;
        } else {
            insert(prefixSum, current);
        }
        
        current = current->next;
    }
    
    // Convert back to array
    int count = 0;
    current = newDummy->next;
    while (current) {
        count++;
        current = current->next;
    }
    
    if (count == 0) return NULL;
    
    int* result = malloc(count * sizeof(int));
    current = newDummy->next;
    for (int i = 0; i < count; i++) {
        result[i] = current->val;
        current = current->next;
    }
    
    *returnSize = count;
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int head[1000];
    int headSize = 0;
    
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        head[headSize++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    int returnSize;
    int* result = solution(head, headSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single traversal through the list, hash map operations are O(1)

✓ Linear Growth

Space Complexity

O(n)

Hash map stores up to n prefix sums in worst case

⚡ Linearithmic Space

32.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map - Prefix Sum Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler