LeetCode Entry
2181. Merge Nodes in Between Zeros
Collapse in-between 0 nodes in a LinkedList list
2181. Merge Nodes in Between Zeros medium
blog post
substack
youtube
https://t.me/leetcode_daily_unstoppable/659
Problem TLDR
Collapse in-between 0 nodes in a LinkedList #medium #linked_list
Intuition
Just do what is asked: iterate and modify the values and links on the fly.
Approach
- Kotlin: let’s use just one extra variable
- Rust: I am sorry
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(1)\)
Code
fun mergeNodes(head: ListNode?): ListNode? {
var curr = head?.next
while (curr?.next != null)
if (curr.next?.`val` ?: 0 > 0) {
curr.`val` += curr.next?.`val` ?: 0
curr.next = curr.next?.next
} else {
curr.next = curr.next?.next
curr = curr.next
}
return head?.next
}
pub fn merge_nodes(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let Some(head_box) = head.as_mut() else { return head };
let mut curr = &mut head_box.next;
while let Some(curr_box) = curr {
let Some(next_box) = curr_box.next.as_mut() else { curr_box.next = None; break };
if next_box.val > 0 {
curr_box.val += next_box.val;
curr_box.next = next_box.next.take()
} else {
curr_box.next = next_box.next.take();
curr = &mut curr.as_mut().unwrap().next
}
}
head.unwrap().next
}