You are given the head of a linked list, which contains a series of integers separated by 0's. The beginning and end of the linked list will have Node.val == 0.
For every two consecutive 0's, merge all the nodes lying in between them into a single node whose value is the sum of all the merged nodes. The modified list should not contain any 0's.
Return the head of the modified linked list.
Example 1:
Input: head = [0,3,1,0,4,5,2,0] Output: [4,11] Explanation: The above figure represents the given linked list. The modified list contains - The sum of the nodes marked in green: 3 + 1 = 4. - The sum of the nodes marked in red: 4 + 5 + 2 = 11.
Example 2:
Input: head = [0,1,0,3,0,2,2,0] Output: [1,3,4] Explanation: The above figure represents the given linked list. The modified list contains - The sum of the nodes marked in green: 1 = 1. - The sum of the nodes marked in red: 3 = 3. - The sum of the nodes marked in yellow: 2 + 2 = 4.
Constraints:
- The number of nodes in the list is in the range
[3, 2 * 105]. 0 <= Node.val <= 1000- There are no two consecutive nodes with
Node.val == 0. - The beginning and end of the linked list have
Node.val == 0.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = tail = ListNode()
s = 0
cur = head.next
while cur:
if cur.val != 0:
s += cur.val
else:
tail.next = ListNode(s)
tail = tail.next
s = 0
cur = cur.next
return dummy.next/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeNodes(ListNode head) {
ListNode dummy = new ListNode();
int s = 0;
ListNode tail = dummy;
for (ListNode cur = head.next; cur != null; cur = cur.next) {
if (cur.val != 0) {
s += cur.val;
} else {
tail.next = new ListNode(s);
tail = tail.next;
s = 0;
}
}
return dummy.next;
}
}/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function mergeNodes(head: ListNode | null): ListNode | null {
let dummy = new ListNode(-1);
let p = dummy;
let sum = 0;
head = head.next;
while (head != null) {
let cur = head.val;
if (cur) {
sum += cur;
} else {
p.next = new ListNode(sum);
p = p.next;
sum = 0;
}
head = head.next;
}
return dummy.next;
}/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeNodes(ListNode* head) {
ListNode* dummy = new ListNode();
ListNode* tail = dummy;
int s = 0;
for (ListNode* cur = head->next; cur; cur = cur->next) {
if (cur->val)
s += cur->val;
else {
tail->next = new ListNode(s);
tail = tail->next;
s = 0;
}
}
return dummy->next;
}
};/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeNodes(head *ListNode) *ListNode {
dummy := &ListNode{}
tail := dummy
s := 0
for cur := head.Next; cur != nil; cur = cur.Next {
if cur.Val != 0 {
s += cur.Val
} else {
tail.Next = &ListNode{Val: s}
tail = tail.Next
s = 0
}
}
return dummy.Next
}