1. 题目描述

定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

2. 思路描述

思路一：经典的“链表头插法”，时间复杂度是 $O(N)$，但是空间复杂度也是 $O(N)$

思路二：链表原地操作，时间复杂度是 $O(N)$，但是空间复杂度只有 $O(1)$。

  1. 保存当前节点node的上一个节点pre
  2. 节点node的next指向pre
  3. 分别将pre和node向后移动 1 个位置
  • 如果node为 null，链表翻转完毕，此时pre指向新的头节点，返回即可
  • 否则，回到第 1 步继续执行

3. 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * 节点定义
 */
class Node {
    constructor(value, next) {
        this.value = value
        this.next = next
    }
}

/**
 * 翻转链表
 * @param {Node} head 未翻转链表的头节点
 * @return {Node} 翻转链表后的头节点
 */
function reverseList(head) {
    let node = head,
        pre = null

    while (node) {
        let next = node.next

        node.next = pre

        pre = node
        node = next
    }

    return pre
}

/**
 * 以下是测试代码, 分别输出倒数第2、3和5个节点
 */

let node3 = new Node(3, null),
    node2 = new Node(2, node3),
    node1 = new Node(1, node2),
    head = new Node(0, node1)

let newHead = reverseList(head)
while (newHead) {
    console.log(newHead)
    newHead = newHead.next
}