1669. Merge In Between Linked Lists

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

Rust Solution

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);
}

Having problems with this solution? Click here to submit an issue on github.