Merge Nodes In Between Zeros — Pointer Walk
Advertisement
Problem 237 · Merge Nodes In Between Zeros
Difficulty: Medium · Pattern: Pointer Walk + Accumulate
Solutions
# Python
def mergeNodes(head):
cur = head.next # skip leading 0
modify = head # where to write sums
total = 0
while cur:
if cur.val == 0:
modify.next = cur if cur.next else None
modify.val = total
modify = modify.next
total = 0
else:
total += cur.val
cur = cur.next
return head
// Java
public ListNode mergeNodes(ListNode head) {
ListNode cur = head.next, modify = head;
int total = 0;
while (cur != null) {
if (cur.val == 0) {
modify.val = total;
modify.next = cur.next != null ? cur : null;
modify = modify.next;
total = 0;
} else total += cur.val;
cur = cur.next;
}
return head;
}
Complexity
- Time: O(n)
- Space: O(1)
Advertisement