1669.合并两个链表

链接：1669.合并两个链表
难度：Medium
标签：链表
简介：给你两个链表 list1 和 list2 ，它们包含的元素分别为 n 个和 m 个。请你将 list1 中下标从 a 到 b 的全部节点都删除，并将list2 接在被删除节点的位置。

题解 1 - cpp

• 编辑时间：2023-01-30
• 执行用时：260ms
• 内存消耗：92.2MB
• 编程语言：cpp
• 解法介绍：双指针。

class Solution {
public:
    ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
        ListNode *p1 = list1, *p2 = list2, *tmp;
        for (int i = 0; i < a - 1; i++) p1 = p1->next;
        tmp = p1->next;
        p1->next = list2;
        p1 = tmp;
        while (p2->next) p2 = p2->next;
        for (int i = 0; i < b - a; i++) p1 = p1->next;
        p2->next = p1->next;
        return list1;
    }
};

题解 2 - rust

• 编辑时间：2023-01-30
• 执行用时：52ms
• 内存消耗：3.6MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn merge_in_between(
        list1: Option<Box<ListNode>>,
        a: i32,
        b: i32,
        list2: Option<Box<ListNode>>,
    ) -> Option<Box<ListNode>> {
        let mut list = Vec::<i32>::new();
        let mut p1 = &list1;
        let mut p2 = &list2;
        for _ in 0..a {
            list.push(p1.as_ref().unwrap().val);
            p1 = &p1.as_ref().unwrap().next;
        }
        while let Some(ref node) = p2 {
            list.push(node.val);
            p2 = &node.next;
        }
        for _ in a..=b {
            p1 = &p1.as_ref().unwrap().next;
        }
        while let Some(ref node) = p1 {
            list.push(node.val);
            p1 = &node.next;
        }
        let mut ans = Box::new(ListNode::new(0));
        let mut p = &mut ans;
        for num in list {
            let mut node = p.as_mut();
            node.next = Some(Box::new(ListNode::new(num)));
            p = node.next.as_mut().unwrap();
        }
        ans.next
    }
}

题解 3 - python

• 编辑时间：2023-01-30
• 执行用时：372ms
• 内存消耗：21.8MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:
        p1, p2 = list1, list2
        for _ in range(a - 1):
            p1 = p1.next
        tmp = p1.next
        p1.next = list2
        p1 = tmp
        while p2.next:
            p2 = p2.next
        for _ in range(b - a):
            p1 = p1.next
        p2.next = p1.next
        return list1