资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

反转链表的三种方法--面试必考（图例超详细解析，小白一看就会）

创作时间:

作者:

@小白创作中心

反转链表的三种方法--面试必考（图例超详细解析，小白一看就会）

引用

CSDN

https://blog.csdn.net/weixin_45031801/article/details/139496847

一、前言

反转链表这道题可以说是链表专题中最经典的一道题，也是面试中频率最高的一道题目。通常在面试中，面试官可能会要求我们写出多种解法来实现这道题目，因此大家需要对这道题目非常熟悉。

本篇博客就来详细讲解一下反转链表的多种实现方法，让我们的面试变得更加顺利。

二、题目描述

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

三、解题方法

⭐ 头插法 --- 创建新的链表

头插这种方法，就是将结点一一地插入到新链表的头前，所以我们需要先去建立出一个新的链表头，也就是下面的这个 rhead，通过遍历原先的链表将这些结点一一转移过去即可。

定义三个变量：cur、newnode、rhead
cur：用于遍历整个旧链表
newnode：用于记录 cur 的下一个节点，防止旧链表找不到
rhead：新链表的头节点

// 重新创建一个链表，将之前的链表进行头插即可
struct ListNode* rphead = NULL;
// 进行指针变换
struct ListNode* cur = head;

开始头插，cur 节点的 next 指向 rhead 节点，然后更新 rhead、cur、newnode 这三个节点

// 用于保存下一个节点地址
struct ListNode* newnode = cur->next;
// 头插
cur->next = rphead;
rphead = cur;
cur = newnode;

继续同样的操作

此时当 cur == NULL 时，便结束一个遍历，然后新链表的头就是 rhead，返回即可

完整代码：

struct ListNode* reverseList(struct ListNode* head)
{
    // 重新创建一个链表，将之前的链表进行头插即可
    struct ListNode* rphead = nullptr;
    // 进行指针变换
    struct ListNode* cur = head;
    while(cur!=NULL)
    {
        // 用于保存下一个节点地址
        struct ListNode* newnode = cur->next;
        // 头插
       cur->next = rphead;
       rphead = cur;
       cur = newnode;
    }
    return rphead;
}

⭐ 迭代法 --- 三指针

三指针的迭代方法，这种方法不需要在去创建一个新的头结点指针，只需要在原先的链表上进行一个操作即可，也就是定义三个指针。

cur：指向当前链表的头
nextnode：指向 cur 的 next，一样是用于保存。
prev：这个的话其实是用来算作链表最后一个结点指向空的。

ListNode* prev = nullptr;
ListNode* cur = head;
ListNode* nextNode = cur->next;

然后将 cur->next = prev，让原本的头 cur 作为反转后新链表的尾巴

接着就是进行的一个迭代操作，首先将 cur 当前的值给到 prev，然后将 nextnode 当前的值给到 cur，然后让 nextnode 继续向下，这个时候其实就进行了一个迭代的操作

cur->next = prev;
prev = cur;
cur = nextnode;

然后继续做翻转，让 cur->next 指向 prev，并更新三个指针

可以看到，当这个 cur == NULL 时，整个链表便完成了一个翻转，此时便结束循环迭代的逻辑

然后可以看到，此时新链表的头并不是 cur，而是 prev，所以最后应该返回 prev

完整代码：

class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        // 1. 迭代法
        // 定义三个指针
        ListNode* prev = nullptr;      // cur 的前一个节点
        ListNode* cur = head;
        // 开始迭代
        while(cur!=nullptr)
        {
            ListNode* nextnode = cur->next;  // cur的下一个指针
            cur->next = prev;
            prev = cur;
            cur = nextnode;
        }
        return prev;
    }
};

⭐ 递归法

我们可以通过迭代的方法来得到递归方法

函数声明中 prev 指针指向的为 NULL，cur 指针指向的为 head，正如递归中声明并初始化的 prev 和 cur 指针
递归结束条件为 cur 为 NULL，返回 prev
同样 newnode 保存 cur 的下一个节点，以防止反转时丢失链表信息。
然后进行反转 cur->next = prev；
prev 为当前已反转部分的头节点，cur 为当前待反转的节点。
然后调用递归，将 cur 作为新的 prev 传入下一层，将 newnode 作为新的 cur 传入下一层。
实现了链表的递归反转

class Solution {
public:
    ListNode* reverse(ListNode* prev, ListNode* cur)
    {
        // 最终结束条件
        if(cur==nullptr)
        {
            return prev;
        }
        ListNode* newnode =cur->next;
        cur->next = prev;
        // 将 cur 作为 prev 传入下一层
        // 将 newnode 作为 cur 传入下一层，改变其指针指向当前 cur
        return reverse(cur,newnode);
    }
    ListNode* reverseList(ListNode* head) 
    {
        // 3. 递归法
        return reverse(nullptr,head);
    }
};