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
.
Solution: List
Skip the first zero, replace every zero node with the sum of values of its previous nodes.
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua class Solution { public: ListNode* mergeNodes(ListNode* head) { ListNode dummy; head = head->next; for (ListNode* prev = &dummy; head; head = head->next) { int sum = 0; while (head->val != 0) { sum += head->val; head = head->next; } prev->next = head; head->val = sum; prev = head; } return dummy.next; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment