-
Notifications
You must be signed in to change notification settings - Fork 27
/
Copy path1171.RemoveZeroSumConsecutiveNodesfromLinkedList.py
66 lines (59 loc) · 1.94 KB
/
1171.RemoveZeroSumConsecutiveNodesfromLinkedList.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
"""
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:
Input: head = [1,2,-3,3,1]
Output: [3,1]
Note: The answer [1,2,1] would also be accepted.
Example:
Input: head = [1,2,3,-3,4]
Output: [1,2,4]
Example:
Input: head = [1,2,3,-3,-2]
Output: [1]
Constraints:
- The given linked list will contain between 1 and 1000 nodes.
- Each node in the linked list has -1000 <= node.val <= 1000.
"""
#Difficulty: Medium
#105 / 105 test cases passed.
#Runtime: 5392 ms
#Memory Usage: 14.1 MB
#Runtime: 5392 ms, faster than 5.07% of Python3 online submissions for Remove Zero Sum Consecutive Nodes from Linked List.
#Memory Usage: 14.1 MB, less than 48.68% of Python3 online submissions for Remove Zero Sum Consecutive Nodes from Linked List.
# 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: ListNode) -> ListNode:
stack = []
while head:
if head.val != 0:
stack.append(head.val)
head = head.next
i = 0
j = 0
l = len(stack)
while i < l:
if sum(stack[i:j+1]) == 0:
stack = stack[:i] + stack[j+1:]
j = i
l = len(stack)
if j == l:
j = i
i += 1
j += 1
if not stack:
return None
node = ListNode(stack.pop(0))
head = node
while stack:
node.next = ListNode(stack.pop(0))
node = node.next
return head