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才能完成。