如何在Rust中手动实现链表复制（不使用.clone()方法）

针对你给出的ListNode结构，我们可以通过遍历原链表、逐个创建新节点并维护新链表的链接关系来实现不依赖.clone()的复制方法。核心思路是利用Rust的引用和可变指针遍历原链表，同时构建新链表的每个节点并依次链接。

以下是具体实现：

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    pub fn new(val: i32) -> Self {
        ListNode {
            val,
            next: None,
        }
    }

    pub fn copyList(head: &Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        // 处理空链表的情况
        let mut original_ptr = head.as_ref();
        if original_ptr.is_none() {
            return None;
        }

        // 创建新链表的头节点
        let mut new_head = Some(Box::new(ListNode::new(original_ptr.unwrap().val)));
        let mut new_tail = new_head.as_mut();

        // 移动原链表指针到下一个节点
        original_ptr = original_ptr.unwrap().next.as_ref();

        // 遍历剩余节点
        while let Some(node) = original_ptr {
            // 创建新节点
            let new_node = Box::new(ListNode::new(node.val));
            // 将新节点链接到新链表尾部
            new_tail.as_mut().unwrap().next = Some(new_node);
            // 移动新链表尾指针到新节点
            new_tail = new_tail.unwrap().next.as_mut();
            // 移动原链表指针到下一个节点
            original_ptr = node.next.as_ref();
        }

        new_head
    }
}

关键细节说明： #

• 空链表处理：先判断原链表是否为空，直接返回None避免后续不必要的操作。
• 指针遍历：使用as_ref()获取原链表节点的不可变引用，避免转移所有权；新链表的尾指针使用as_mut()获取可变引用，以便修改next字段链接新节点。
• 节点创建与链接：每次遍历原节点时，创建对应值的新节点，将其赋值给当前尾节点的next，再更新尾指针到新节点，完成链表的逐步构建。

这种实现的时间复杂度为O(n)（n为链表节点数），空间复杂度为O(n)（需要存储所有新创建的节点），完全符合手动复制链表的需求。

内容的提问来源于stack exchange，提问作者Bird