反转链表

Tips

题目类型: LinkedList

相关题目:

• 25. k-个一组翻转链表
• 92. 反转链表-ii

题目

反转一个单链表.

示例

输入: 1->2->3->4->5->NULL

输出: 5->4->3->2->1->NULL

题解

迭代法

对于 1->2->3->null 的反转, 实际上就变成了 null<-1<-2<-3, 因此初始化一个 prev 为 null, 让:

curr.next = prev
prev = curr

但是 curr.next = prev 这句会导致 curr.next 丢失了, 因为它已经被赋值给了 prev, 因此需要先将 curr.next 存储下来, 反转之后将 curr.next 赋值给 curr.

JavaScript - 迭代

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
  let prev = null

  while (head) {
    const tmp = head.next
    head.next = prev
    prev = head
    head = tmp
  }

  return prev
}

时间复杂度: O(n), 其中 n 是链表的长度. 需要遍历链表一次.

空间复杂度: O(1).

JavaScript - 递归

我们可以把这个问题拆解成两个子问题, 分别是头节点, 以及头节点后面节点的反转.

• 递的过程: 一直找到尾部节点
• 归的过程: 以图片中倒数第二个 78(head) -> 99 -> null 为例, 实际上就是将 head.next.next = head, 并将 head.next = null

var reverseList = function (head) {
  if (head === null || head.next === null) return head

  const last = reverseList(head.next) // 递的过程: 找到尾部节点

  // 归的过程: 将尾部节点的 next 设为 head
  head.next.next = head
  // 并将 head 的 next 设为 null
  head.next = null

  return last
}

时间复杂度: O(n), 其中 n 是链表的长度. 需要对链表的每个节点进行反转操作.

空间复杂度: O(n), 其中 n 是链表的长度. 空间复杂度主要取决于递归调用的栈空间, 最多为 n 层.

Rust

// 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
//     }
//   }
// }

pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut prev = None;
    let mut curr = head;

    while curr.is_some() {
        let mut tmp = curr.take().unwrap();
        curr = tmp.next;
        tmp.next = prev;
        prev = Some(tmp);
    }

    prev
}