2020/2/7
题目描述
- 反转一个单链表。
示例
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
相关标签
链表
解题思路
除了记录链表中的每一个值到Vec中，然后重新生成链表的暴.力法以外（O(2n)，O(n)）。还有两种更快的方法可以采用，分别是迭代法和递归法。
迭代法
在遍历链表时，将当前节点的next指针指向前一个元素，第一个节点的next指针需要指向None。另外还需要一个指针来存储下一个节点。
- 时间复杂度：O(n)，假设n为列表的长度，时间复杂度为O(n)。
- 空间复杂度：O(1)。递归法
假设链表m的长度为n，其中[i+1, n]部分的已经被反转，那么m[i]节点的指针应该指向None，m[i+1]节点（若存在）的指针应当指向m[i]。以此类推，最终可以得到一个完整的反转链表。
- 时间复杂度：O(n)，假设n为列表的长度，时间复杂度为O(n)。
- 空间复杂度：O(n)，由于使用递归，将会使用隐式栈空间，递归深度可能达到n层。
源代码
迭代法
// 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>> {
if(head==None){
return None;
}
// 存放当前节点的next指针指向的节点
let mut node_p1: Option<Box<ListNode>> = None;
// 存放下一个节点
let mut node_p2 = &head;
while let Some(node) = node_p2{
node_p1 = Some(Box::new(ListNode {
next: node_p1,
val: node.val}));
node_p2 = &node.next;
}
node_p1
}
}
- 执行用时 :0 ms, 在所有 Rust 提交中击败了100.00%的用户
- 内存消耗 :2.4 MB, 在所有 Rust 提交中击败了44.00%的用户
递归法
use List::*;
// 链表结构
#[derive(Debug)]
enum List {
Cons1(i32, Box<List>),
Nil,
}
// Methods can be attached to an enum
impl List {
#[inline]
fn new() -> List {
Nil
}
// 在当前节点前新增节点
#[inline]
fn prepend(self, elem: i32) -> List {
Cons1(elem, Box::new(self))
}
// 获取链表长度
fn len(&self) -> i32 {
match *self {
Cons1(_, ref tail) => 1 + tail.len(),
Nil => 0
}
}
// 将链表转化为字符串
fn stringify(&self) -> String {
match
*self {
Cons1(head, ref tail) => {
format!("{}, {}", head, tail.stringify())
},
Nil => {
format!("Nil")
},
}
}
}
// 反转链表
fn reverse_list(list:List, acc:List ) -> List{
match list{
Cons1(val,tail) => {
reverse_list(*tail,acc.prepend(val))
}
Nil => acc
}
}
fn main() {
let mut head = List::new();
let mut i=0;
while i < 10 {
i+=1;
head = head.prepend(i);
}
println!("{:30}",head.stringify());-
let result = List::new();
let result = reverse_list(head,result);
println!("{}", result.stringify());
}
在不修改原题目函数签名的情况下难以完成, 目前可以通过采用std::List来实现，另外也可以通过unsafe的裸指针来尝试实现，待续。
总结
Rust由于所有权检查的存在，对于链表的操作相较于别的语言会复杂一些。部分情况下可能需要使用unsafe才能完成。
