引言

大家好啊，我是前端拿破轮😁。

跟着卡哥学算法有一段时间了，通过代码随想录的学习，受益匪浅，首先向卡哥致敬🫡。

但是在学习过程中我也发现了一些问题，很多当时理解了并且AC的题目过一段时间就又忘记了，或者不能完美的写出来。根据费曼学习法，光有输入的知识掌握的是不够牢靠的，所以我决定按照代码随想录的顺序，输出自己的刷题总结和思考。同时，由于以前学习过程使用的是JavaScript,而在2025年的今天，TypeScript几乎成了必备项，所以本专题内容也将使用TypeScript，来巩固自己的TypeScript语言能力。

题目信息

反转链表

leetcode题目链接

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

题目分析

本题考查对链表的基本操作，反转链表，有递归和迭代两种实现方式。

在解答该题时，并不需要使用虚拟头结点，因为反转链表时，不需要改变链表的头结点，只需要改变链表的指向即可。

题解

迭代法

迭代法中使用双指针，一个指针cur指向当前节点，一个指针pre指向前一个节点，当遍历到最后，cur指向null的时候，pre就是反转后的链表头结点。

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
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function reverseList(head: ListNode | null): ListNode | null {
    // 剪枝
    if (!head || !head.next) return head;

    // 前一个值
    let pre = null;

    // 当前值
    let cur = head;

    while (cur) {
        // 保存下一个值
        const next = cur.next;

        // 反转
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
};

递归法

因为链表的结构在定义上是递归的，所以很多题目可以用递归法来解决。

递归的时候，要分析清除递归三部曲：

  1. 确定递归函数的参数和返回值:确定哪些参数是递归过程中需要处理的，那么就在递归函数里面加上这个参数，并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
  2. 确定终止条件：写完了递归算法，运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈结构来存储每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
  3. 确定单层递归逻辑: 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。单层递归也需要确认返回值。

所以在本题来看，依次进行三部曲

  1. 递归函数reverseList，参数为head，返回值也为head,head可以是ListNode或者null
  2. 确定终止条件，当head或者head.next为null时，返回head。
  3. 确定单层递归逻辑，在每一层中先将head.next为首的链表反转，再将head连接到反转后的链表末尾，再把head.next设置为null,并返回反转后的链表头。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function reverseList(head: ListNode | null): ListNode | null {
    if (!head || !head.next) return head;

    const newList = reverseList(head.next);
    head.next.next = head;

    head.next = null;

    return newList;
};

总结

本题不是严格的算法题目，考查对链表基础知识的掌握和理解。在反转链表时，有两种方式，一种是递归，一种是迭代。递归法要按照递归三部曲来进行，才不会混乱，要注意反转后将head.next设置为null,否则会导致链表成环。迭代法使用使用双指针来实现反转。

好了，这篇文章就到这里啦，如果对您有所帮助，欢迎点赞,收藏,分享👍👍👍。您的认可是我更新的最大动力。

往期推荐✨✨✨

我是前端拿破轮，关注我，和您分享前端知识，我们下期见！