Difficulty: 🟡 Medium
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.
- The number of nodes in the list is in the range
[3, 2 * 10^5]
. 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]:
target = head
while target and target.next:
if target.next.val:
target.val += target.next.val
target.next = target.next.next
else:
if target.next.next is None:
target.next = None
target = target.next
return head
The given solution iterates through the linked list and merges consecutive nodes with non-zero values. It modifies the list in-place by updating the values and next pointers.
The algorithm works as follows:
- Initialize a pointer,
target
, to the head of the linked list. - Iterate through the linked list while
target
andtarget.next
are not None:- If
target.next.val
is non-zero, add its value to the currenttarget
node's value, and update the next pointer oftarget
totarget.next.next
(skipping the next node). - If
target.next.val
is zero, movetarget
to the next node.
- If
- Return the head of the modified linked list.
The algorithm merges the nodes in-place, eliminating the need for extra space.
The time complexity of this algorithm is O(n), where n is the number of nodes in the linked list. The algorithm iterates through the list once, and each iteration takes constant time.
The space complexity of the algorithm is O(1) since it only uses a constant amount of extra space to store the pointers.
The given solution modifies the linked list by merging consecutive non-zero nodes and removing the merged nodes. It has a time complexity of O(n) and a space complexity of O(1), making it an efficient solution for the problem at hand.
NB: If you want to get community points please suggest solutions in other languages as merge requests.