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.
合并零之间的节点。
给你一个链表的头节点 head ,该链表包含由 0 分隔开的一连串整数。链表的 开端 和 末尾 的节点都满足 Node.val == 0 。对于每两个相邻的 0 ,请你将它们之间的所有节点合并成一个节点,其值是所有已合并节点的值之和。然后将所有 0 移除,修改后的链表不应该含有任何 0 。
返回修改后链表的头节点 head 。
思路
这是链表类的简单题,请直接参考代码注释。
复杂度
时间O(n)
空间O(1)
代码
Java实现
/**
* 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(0);
ListNode p = dummy;
ListNode cur = head;
int sum = 0;
while (cur != null) {
// 遇到0就开始计算0之间的node的和
if (cur.val == 0) {
sum = 0;
cur = cur.next;
while (cur != null && cur.val != 0) {
sum += cur.val;
cur = cur.next;
}
// 遇到下一个0或者list结尾就把之前计算的和放到新的node中
if (sum != 0) {
p.next = new ListNode(sum);
p = p.next;
}
} else {
cur = cur.next;
}
}
return dummy.next;
}
}
标签:ListNode,cur,val,sum,list,next,Merge,2181,Zeros
From: https://www.cnblogs.com/cnoodle/p/18404076