描述

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

示例 1:

输入:head = [1,2,3,4,5] 输出:[5,4,3,2,1]

示例 2:

输入:head = [1,2] 输出:[2,1]

示例 3:

输入:head = [] 输出:[]

进阶:链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题?

解法

递归

首先想到的是递归,将大问题缩小大小问题,然后在逐步解决。 以[1,2]=>[2,1]为例:

let node1 = { val: 1, next: node2 };
let node2 = { val: 2, next: null };
// 将 [1,2]反转为[2,1]
let node1 = { val: 1, next: null };
let node2 = { val: 2, next: node1 };
1
2
3
4
5

这一步中,进行的操作是:

  1. node2(node1.next).next = node1;
  2. node1.next = null;

边界条件是:当 node 本身 或者 node.next 为 null 时,其实就是最后一个,就不必再进行下一步操作了。

function reverseList(head: ListNode | null): ListNode | null {
  if (head == null || head.next == null) {
    // 判断边界条件
    return head;
  }
  // 拿到下一个的递归node
  const newHead = reverseList(head.next);
  // 重复赋值和断开操作
  head.next.next = head;
  head.next = null;
  // 返回操作后的值
  return newHead;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

迭代

迭代的思路是一样的,先赋值,然后在断开与上一个的链接。

// let node = {val: 1,next: {val: 2,next: null}}
function reverseList(head: ListNode | null): ListNode | null {
  let current = head; // 当前节点
  let prev = null; // 当前节点的前一个节点prev
  while (current) {
    // 保存当前节点的next
    let temp = current.next;
    // 将当前节点的next指向前一个节点
    current.next = prev; 
    // 更新上一个节点
    prev = current; 
    // 更新current
    current = temp;
  }
  return prev;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

参考

  • https://juejin.cn/post/6844904184941117448
上次更新: 8/13/2022, 9:55:10 AM
Contributors: 九旬