Remove Zero Sum Consecutive Nodes from Linked List — LeetCode 1171 Python Solution
MediumHash TableLinked List
- Problem
- #1171
- Pattern
- Linked List
- Reading time
- 4 min
- Source
- leetcode.com
The 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.
Example
- Input
- head = [1,2,-3,3,1]
- Output
- [3,1]
Python solution
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(next=head)
last = {}
s, cur = 0, dummy
while cur:
s += cur.val
last[s] = cur
cur = cur.next
s, cur = 0, dummy
while cur:
s += cur.val
cur.next = last[s].next
cur = cur.next
return dummy.nextComplexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Linked List
Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 1171. Remove Zero Sum Consecutive Nodes from Linked List is filed here because LeetCode tags it Linked List, which is the vocabulary this hub collects.
The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 1171. Remove Zero Sum Consecutive Nodes from Linked List?
- LeetCode 1171. Remove Zero Sum Consecutive Nodes from Linked List is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1171. Remove Zero Sum Consecutive Nodes from Linked List?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 1171. Remove Zero Sum Consecutive Nodes from Linked List?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1171. Remove Zero Sum Consecutive Nodes from Linked List cover?
- LeetCode 1171. Remove Zero Sum Consecutive Nodes from Linked List is tagged Hash Table and Linked List on LeetCode.