如何在Rust中反转部分链表？

s5a0g9ez 于 2023-08-05 发布在其他

关注(0)|答案(1)|浏览(86)

我解决这个leetcode任务https://leetcode.com/problems/reverse-linked-list-ii/description/
主要思想是在范围[左; right]我的代码：（想法是存储left之前的节点和right之后的节点。使用函数反转范围，最后将尾部追加到反转后的列表中）
Algorithm is ok bit I have problems with Rust implementation：

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
// 
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
    pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut curr = head;
        let mut prev = None;
        let mut next;

        while let Some(mut node) = curr {
            next = node.next;
            node.next = prev;
            prev = Some(node);
            curr = next;
        }
        return prev;
    }

    pub fn reverse_between(head: Option<Box<ListNode>>, left: i32, right: i32) -> Option<Box<ListNode>> {
        let mut fake_head = Box::new(ListNode::new(-1));
        fake_head.next = head;
    
        let mut curr = fake_head.as_mut();
        let mut tail = fake_head.clone();

    

        for i in 0..=right {
            if i < left - 1{
                curr = curr.next.as_mut().unwrap();
            }
            tail = tail.next.unwrap();
        }
        let mut reversed = Self::reverse_list(curr.next);
        fake_head.next = reversed;
        while reversed.unwrap().next.is_some() {
            reversed = reversed.unwrap().next;
        }
        reversed.unwrap().next = Some(tail);
        return fake_head.next;
    }
}

字符串
我有一个错误：

Line 37, Char 24: cannot borrow `fake_head` as immutable because it is also borrowed as mutable (solution.rs)
   |
36 |         let mut curr = fake_head.as_mut();
   |                        ------------------ mutable borrow occurs here
37 |         let mut tail = fake_head.clone();
   |                        ^^^^^^^^^^^^^^^^^ immutable borrow occurs here
...
47 |         let mut reversed = Self::reverse_list(curr.next);
   |                                               --------- mutable borrow later used here
Line 47, Char 47: cannot move out of `curr.next` which is behind a mutable reference (solution.rs)
   |
47 |         let mut reversed = Self::reverse_list(curr.next);
   |                                               ^^^^^^^^^ move occurs because `curr.next` has type `Option<Box<list_node::ListNode>>`, which does not implement the `Copy` trait
   |

型
你能告诉我如何改进我的代码并修复错误吗？

rust

来源：https://stackoverflow.com/questions/76697406/how-to-reverse-part-of-linked-list-in-rust

1条答案

按热度按时间

ui7jx7zq1#

假设你下面的struct为ListNode。

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

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

    pub fn take_next(&mut self) -> Option<Box<ListNode>> {
        mem::replace(&mut self.next, None)
    }

    pub fn next(&self) -> &Box<ListNode> {
        self.next.as_ref().unwrap()
    }

    pub fn next_mut(&mut self) -> &mut Box<ListNode> {
        self.next.as_mut().unwrap()
    }

    pub fn tail(&mut self, next: Option<Box<ListNode>>) {
        self.next = next;
    }
}

字符串
这允许简化代码并通过指针链进行更多工作，而不必使指针指向列表中的不同点。

pub fn reverse_between(head: Option<Box<ListNode>>, left: i32, right: i32) -> Option<Box<ListNode>> {
    let mut fake_head = Box::new(ListNode::new(-1));
    fake_head.next = head;

    let mut curr = &mut fake_head;
    for _ in 0..left {
        curr = curr.next_mut();
    }

    let mut reverse = curr.take_next().unwrap();
    let tail = {
        let mut n = reverse.as_mut();
        for _ in left..right {
            n = n.next_mut();
        }
        n.take_next()
    };

    let reversed = reverse_list(Some(reverse));
    curr.next = reversed;

    while curr.next.is_some() {
        curr = curr.next_mut();
    }
    curr.tail(tail);
    return fake_head.next;
}

型

赞(0）回复(0）举报 2023-08-05

我来回答

如何在Rust中反转部分链表？

1条答案

相关问题

热门标签

最新问答