LeetCode Entry
1669. Merge In Between Linked Lists
Replace a segment in a LinkedList
1669. Merge In Between Linked Lists medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/544
Problem TLDR
Replace a segment in a LinkedList #medium
Intuition
Just careful pointers iteration.
Approach
- use dummy to handle the first node removal
- better to write a separate cycles
- Rust is hard
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(1)\)
Code
fun mergeInBetween(list1: ListNode?, a: Int, b: Int, list2: ListNode?) =
ListNode(0).run {
next = list1
var curr: ListNode? = this
for (i in 1..a) curr = curr?.next
var after = curr?.next
for (i in a..b) after = after?.next
curr?.next = list2
while (curr?.next != null) curr = curr?.next
curr?.next = after
next
}
pub fn merge_in_between(list1: Option<Box<ListNode>>, a: i32, b: i32, list2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut dummy = Box::new(ListNode::new(0));
dummy.next = list1;
let mut curr = &mut dummy;
for _ in 0..a { curr = curr.next.as_mut().unwrap() }
let mut after = &mut curr.next;
for _ in a..=b { after = &mut after.as_mut().unwrap().next }
let after_b = after.take(); // Detach the rest of the list after `b`, this will allow the next line for the borrow checker
curr.next = list2;
while let Some(ref mut next) = curr.next { curr = next; }
curr.next = after_b;
dummy.next
}