Description
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.
Solutions
Solution 1: Simulation
We define a dummy head node dummy, a pointer tail pointing to the current node, and a variable s to record the sum of the values of the current nodes.
Next, we traverse the linked list starting from the second node. If the value of the current node is not 0, we add it to s. Otherwise, we add s to the node after tail, set s to 0, and update tail to the next node.
Finally, we return the node next to dummy.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the linked list.
PythonJavaC++GoTypeScriptRustC
# 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:
s += cur.val
else:
tail.next = ListNode(s)
tail = tail.next
s = 0
cur = cur.next
return dummy.next(code-box)
/**
* 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;
}
}(code-box)
/**
* 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;
}
};(code-box)
/**
* 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
}(code-box)
/**
* 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 {
const dummy = new ListNode();
let tail = dummy;
let s = 0;
for (let 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;
}(code-box)
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {
pub fn merge_nodes(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut dummy = Box::new(ListNode::new(0));
let mut tail = &mut dummy;
let mut s = 0;
let mut cur = head.unwrap().next;
while let Some(mut node) = cur {
if node.val != 0 {
s += node.val;
} else {
tail.next = Some(Box::new(ListNode::new(s)));
tail = tail.next.as_mut().unwrap();
s = 0;
}
cur = node.next.take();
}
dummy.next
}
}(code-box)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeNodes(struct ListNode* head) {
struct ListNode dummy;
struct ListNode* cur = &dummy;
int sum = 0;
while (head) {
if (head->val == 0 && sum != 0) {
cur->next = malloc(sizeof(struct ListNode));
cur->next->val = sum;
cur->next->next = NULL;
cur = cur->next;
sum = 0;
}
sum += head->val;
head = head->next;
}
return dummy.next;
}(code-box)
