You are given two linked lists: list1
and list2
of sizes n
and m
respectively.
Remove list1
's nodes from the ath
node to the bth
node, and put list2
in their place.
The blue edges and nodes in the following figure incidate the result:
Build the result list and return its head.
Example 1:
Input: list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002] Output: [0,1,2,1000000,1000001,1000002,5] Explanation: We remove the nodes 3 and 4 and put the entire list2 in their place. The blue edges and nodes in the above figure indicate the result.
Example 2:
Input: list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004] Output: [0,1,1000000,1000001,1000002,1000003,1000004,6] Explanation: The blue edges and nodes in the above figure indicate the result.
Constraints:
3 <= list1.length <= 104
1 <= a <= b < list1.length - 1
1 <= list2.length <= 104
struct Solution;
use rustgym_util::*;
impl Solution {
fn merge_in_between(list1: ListLink, a: i32, b: i32, list2: ListLink) -> ListLink {
let mut l1 = vec![];
let mut l2 = vec![];
let mut p1 = list1;
let start = a as usize;
let end = (b + 1) as usize;
while let Some(mut node) = p1 {
p1 = node.next.take();
l1.push(node);
}
let mut p2 = list2;
while let Some(mut node) = p2 {
p2 = node.next.take();
l2.push(node);
}
let mut prev = None;
for _ in (end..l1.len()).rev() {
let mut node = l1.pop().unwrap();
node.next = prev;
prev = Some(node);
}
for _ in (start..end).rev() {
l1.pop();
}
for _ in (0..l2.len()).rev() {
let mut node = l2.pop().unwrap();
node.next = prev;
prev = Some(node);
}
for _ in (0..start).rev() {
let mut node = l1.pop().unwrap();
node.next = prev;
prev = Some(node);
}
prev
}
}
#[test]
fn test() {
let list1 = list![0, 1, 2, 3, 4, 5];
let a = 3;
let b = 4;
let list2 = list![1000000, 1000001, 1000002];
let res = list![0, 1, 2, 1000000, 1000001, 1000002, 5];
assert_eq!(Solution::merge_in_between(list1, a, b, list2), res);
let list1 = list![0, 1, 2, 3, 4, 5, 6];
let a = 2;
let b = 5;
let list2 = list![1000000, 1000001, 1000002, 1000003, 1000004];
let res = list![0, 1, 1000000, 1000001, 1000002, 1000003, 1000004, 6];
assert_eq!(Solution::merge_in_between(list1, a, b, list2), res);
}