如何在Rust中实现按rank排序的有序单链表？

下面是修复后的完整代码，解决了所有权错误和插入逻辑问题：

use std::fmt;

#[derive(Debug, Clone)]
struct Node {
    rank: u32,
    value: String,
    next: Option<Box<Node>>,
}

impl Node {
    fn new(rank: u32, value: String) -> Self {
        Node { rank, value, next: None }
    }
}

struct SortedLinkedList {
    head: Option<Box<Node>>,
}

impl SortedLinkedList {
    fn new() -> Self {
        SortedLinkedList { head: None }
    }

    // 按rank升序插入，保证pop时取出最小rank节点
    fn push(&mut self, rank: u32, value: String) {
        let new_node = Box::new(Node::new(rank, value));

        // 处理空链表或新节点rank小于头节点的情况
        match &mut self.head {
            None => {
                self.head = Some(new_node);
                return;
            }
            Some(ref mut head_node) if new_node.rank < head_node.rank => {
                let old_head = self.head.take();
                self.head = Some(new_node);
                self.head.as_mut().unwrap().next = old_head;
                return;
            }
            _ => {}
        }

        // 遍历寻找插入位置：找到第一个next节点rank大于新节点的位置
        let mut current = &mut self.head;
        while let Some(ref mut node) = current {
            match &mut node.next {
                None => {
                    // 到链表末尾，直接追加
                    node.next = Some(new_node);
                    break;
                }
                Some(ref mut next_node) if next_node.rank > new_node.rank => {
                    // 插入到当前节点与next节点之间
                    let old_next = node.next.take();
                    node.next = Some(new_node);
                    node.next.as_mut().unwrap().next = old_next;
                    break;
                }
                _ => {
                    // 继续遍历下一个节点
                    current = &mut node.next;
                }
            }
        }
    }

    // 取出rank最小的头节点
    fn pop(&mut self) -> Option<Box<Node>> {
        self.head.take().map(|mut head| {
            self.head = head.next.take();
            head
        })
    }
}

impl fmt::Display for SortedLinkedList {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let mut current = &self.head;
        let mut first = true;
        write!(f, "[")?;
        while let Some(node) = current {
            if !first {
                write!(f, ", ")?;
            }
            write!(f, "(rank: {}, value: {})", node.rank, node.value)?;
            current = &node.next;
            first = false;
        }
        write!(f, "]")
    }
}

fn main() {
    let mut list = SortedLinkedList::new();
    list.push(3, "C".to_string());
    list.push(1, "A".to_string());
    list.push(2, "B".to_string());
    println!("List after pushes: {}", list);
    // 输出：[(rank: 1, value: A), (rank: 2, value: B), (rank: 3, value: C)]

    while let Some(node) = list.pop() {
        println!("Popped: (rank: {}, value: {})", node.rank, node.value);
    }
    // 输出顺序：A, B, C
}

问题修复说明 #

1. 解决E0507所有权错误 #

原代码的核心问题是修改链表节点时，没有正确处理所有权转移与可变引用的冲突：

• 使用take()方法安全取出Option<Box<Node>>内部的值（同时将原位置设为None），避免同一时间存在多个可变引用导致的所有权冲突。
• 替换头节点或插入中间节点时，通过take()转移原有节点的所有权，再重新绑定新的节点关系，符合Rust的所有权规则。

2. 修复插入第三个元素时迭代器提前退出的问题 #

原遍历逻辑存在条件判断漏洞，导致提前终止循环：

• 调整遍历逻辑：从头部开始，持续查找第一个next节点rank大于新节点的位置，或遍历到链表末尾才终止。
• 覆盖了空链表、插入头部、插入中间、插入末尾四种场景，确保所有元素都能找到正确的插入位置。

关键注意事项 #

• 所有权安全：修改链表指针时，必须通过take()或replace()等方法处理Option类型的所有权转移，避免引用悬垂。
• 遍历逻辑严谨：插入排序的核心是精准定位插入位置，需覆盖所有边界场景，防止遗漏或提前终止。

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