Description
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.)
Example 1:
Input: head = [1,2,-3,3,1]
Output: [3,1]
Note: The answer [1,2,1] would also be accepted.
Example 2:
Input: head = [1,2,3,-3,4]
Output: [1,2,4]
Example 3:
Input: head = [1,2,3,-3,-2]
Output: [1]
Constraints:
- The given linked list will contain between
1
and1000
nodes. - Each node in the linked list has
-1000 <= node.val <= 1000
.
Solutions
1. 前缀和-Hash Table
# Time: O(n)
# Space: O(n)
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def removeZeroSumSublists(self, head: ListNode) -> ListNode:
dummy = ListNode(0)
dummy.next = head
sum_hash = collections.defaultdict()
add = 0
sum_hash[0] = dummy
node = head
while node:
add += node.val
if add in sum_hash:
sum_hash[add].next = node.next
sum_hash.clear()
node = dummy
sum_hash[0] = dummy
add = 0
else:
sum_hash[add] = node
node = node.next
return dummy.next
# 105/105 cases passed (52 ms)
# Your runtime beats 24.11 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (13.3 MB)
不从最开始的位置遍历:
# Time: O(n)
# Space: O(n)
class Solution:
def removeZeroSumSublists(self, head: ListNode) -> ListNode:
cur = dummy = ListNode(0)
dummy.next = head
prefix = 0
seen = collections.OrderedDict()
while cur:
prefix += cur.val
node = seen.get(prefix, cur)
while prefix in seen:
seen.popitem()
seen[prefix] = node
node.next = cur = cur.next
return dummy.next
# 105/105 cases passed (48 ms)
# Your runtime beats 28.44 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (13.3 MB)
2. Two Passes
第一遍遍历计算从开始节点开始当当前节点的所有结点的和,有相同也只会更新最近的那个位置,这个位置在第二遍遍历的时候就能直接当做隔空对接的位置!
# Time: O(n)
# Space: O(n)
class Solution:
def removeZeroSumSublists(self, head: ListNode) -> ListNode:
cur = dummy = ListNode(0)
dummy.next = head
prefix = 0
sum_hash = collections.defaultdict()
while cur:
prefix += cur.val
sum_hash[prefix] = cur
cur = cur.next
cur = dummy
prefix = 0
while cur:
prefix += cur.val
cur.next = sum_hash[prefix].next
cur = cur.next
return dummy.next
# 105/105 cases passed (40 ms)
# Your runtime beats 82.67 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (13.2 MB)