07. 反转链表

0 - 算法, 0.0 - 算法模版 本文总阅读量次

正文

反转链表（Reverse Linked List）是链表操作中最基础且最高频的考点。它通过改变节点间的指针指向，将原本 A -> B -> C 的结构变为 C -> B -> A。

算法模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class ListNode(var value: Int) {
    var next: ListNode? = null
}

fun reverseList(head: ListNode?): ListNode? {
    var prev: ListNode? = null
    var current = head
    
    while (current != null) {
        val nextNode = current.next // 1. 暂存下一个节点
        current.next = prev         // 2. 反转当前节点的指向
        prev = current              // 3. prev 向前移动
        current = nextNode          // 4. current 向前移动
    }

    return prev // 新的头节点
}

使用说明

  1. 核心逻辑：
    在遍历过程中，我们需要维持三个变量：prev（已反转部分的头）、current（当前处理的节点）和 nextNode（待处理部分的头）。

  2. 关键步骤：
    反转指针前，**必须先暂存 current.next**，否则一旦修改了 current.next，就无法找到链表的后续部分。

  3. 时间与空间复杂度：

    • 时间复杂度：$O(N)$，只需遍历一次链表。
    • 空间复杂度：$O(1)$，仅需常数级别的额外空间。

  4. 注意点：

    • 空链表或只有一个节点的链表应能正常工作。
    • 在 Kotlin 中，注意处理可空性（ListNode?）。
0 - 算法, 0.0 - 算法模版