学了链表牛刀小试，三种做法都吃透就算是学会了

mynotebook 2023-02-01 发布于湖南

展开全文

大家好，我是梁唐。

今天我们继续来挑战链表，来看一道LeetCode当中的一道经典问题——206.反转链表。

这道题在很多公司的面试和笔试题中都有出现，我就曾经遇到过。绝对算是链表领域的经典例题了，如果最近刚好要参加面试笔试的同学，那么千万不要错过，说不定就遇上了。

我们先来看看题面。

206. 反转链表

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

分析

题面还是比较直接的，就是让我们将一个给定的链表来翻转。

最简单最取巧的方法当然是先遍历一遍链表，将所有元素存进数组之后，再认为构造一个链表。这样做当然不能说不行，只不过在面试当中通常是无法令面试官满意的。

因为我们根本没有利用好给定我们的链表，额外地消耗了内存空间。所以如果在面试当中遇到，面试官是不会只满足于听到这样的回答的。那么，我们又该如何在不创建新链表的前提下完成翻转呢？

对于这个问题，这题很好心地在进阶里面给了我们提示，可以使用迭代或者递归的方法。

我个人感觉这两种方法难度差不多，不过从理解难度上来说，递归的方法更简单直观一些。

递归法

为什么说递归的方法稍微更直观呢？因为我们可以把递归函数本身当成是一个能够在更小范围内运作的黑盒，接着，我们要做的就是像是套娃一样，让它能够在更大的范围当中实现同样的功能。

比如在这题当中，我们要使用递归来实现reverseList函数。我们先假设，它能够在比当前更小的范围内运行。对于当前输入来说是head开头的链表，那么head->next开头的链表就可以看成是比当前范围更小的范围。我们假设reverseList能够将head->next开头的链表翻转，我们要在此基础上构造出以head开头翻转的结果。

假设当前的输入是[1, 2, 3, 4, 5]，当前head指向1。head->next指向[2, 3, 4, 5]。调用reverseList之后可以得到[5, 4, 3, 2]。所以我们要做的把head放到递归结果的末尾。

所以我们要做的就很简单，只有两步。第一步递归调用reverseList，传入head->next拿到结果。第二步，将head插入到递归返回的链表末尾。

由于在本题中链表都是通过头节点表示的，所以我们要先遍历一次到达链表的结尾。不要忘了处理一下边界情况，即head为空或者是head->next为空的情况。

这些都想明白的话，代码自然也就出来了：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 处理边界
        if (head == nullptr || head->next == nullptr) return head;
        // 递归调用
        auto cur = reverseList(head->next);
        // 遍历到链表的最后一个节点
        auto tmp = cur;
        while (tmp->next != nullptr) tmp = tmp->next;
        // 插入head
        tmp->next = head;
        head->next = nullptr;
        return cur;
    }
};

改进

这里我们为了求出链表最后一个节点在递归当中使用了循环，通过遍历的方式去找了最末的节点。

实际上我们大可以不必如此，我们直接让递归函数也返回末尾的指针即可。但这样的话，我们就修改了返回值的类型，所以就要单独写一个递归来实现了。整体的原理和刚才是一样的，只不过我们稍作加工，让递归能够既返回头节点也返回尾节点。我们就不用再去额外遍历了。

下面这段代码的核心逻辑和之前是一样的，只是优化了递归返回的部分。

class Solution {
public:

    pair<ListNode*, ListNode*> reverse(ListNode* head) {
        // 处理边界
        if (head == nullptr || head->next == nullptr) return make_pair(head, head);
        // 递归
        auto tmp = reverse(head->next);
        // 将head插入到末尾
        tmp.second->next = head;
        head->next = nullptr;
        // 返回新结果
        return make_pair(tmp.first, head);
    }

    ListNode* reverseList(ListNode* head) {
        return reverse(head).first;
    }
};

迭代

理解完了递归的做法之后，我们再来思考：如果不使用递归，那么这道题又该怎么解决呢？

其实并不难，只需要理解一点就可以搞定。那就是对于链表来说，我们可以在任何节点插入元素。既然如此，我们既可以每次插入在末尾，自然也可以插入在头部。如果我们每次插入元素都在头部的话，得到的链表中的元素顺序刚好和之前相反。

所以我们只需要再创建一个链表，一边遍历，一边将读取到的元素插入在新链表的头部，最后返回即可。

这里可以使用之前介绍的虚拟头节点的技巧来简化代码：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr) return head;
        auto pt = head;
        // 新链表的虚拟头节点
        auto ret = new ListNode(0);
        while (pt != nullptr) {
            auto cur = pt;
            pt = pt->next;
            // 插入在ret指针之后
            cur->next = ret->next;
            ret->next = cur;
        }
        return ret->next;
    }
};