链表反转的三种方法详解：头插法、迭代法和递归法

链表反转的三种方法详解：头插法、迭代法和递归法

引用

CSDN

1.

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

链表反转是数据结构中一个非常经典的问题，尤其在面试中频繁出现。掌握链表反转的多种方法不仅能提升编程能力，还能在面试中给面试官留下深刻印象。本文将详细讲解链表反转的三种方法：头插法、迭代法和递归法。

一、题目描述

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

二、解题方法

头插法 —— 创建新的链表

头插法的基本思路是将原链表的节点依次插入到新链表的头部。具体步骤如下：

1. 定义三个变量：cur（用于遍历原链表）、newnode（保存cur的下一个节点）和rhead（新链表的头节点）。
2. 遍历原链表，将每个节点插入到新链表的头部。
3. 当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;
}

迭代法 —— 三指针

迭代法不需要创建新的链表，只需要在原链表上操作即可。具体步骤如下：

1. 定义三个指针：cur（当前节点）、nextnode（cur的下一个节点）和prev（前一个节点）。
2. 将cur->next指向prev，实现链表反转。
3. 更新三个指针的位置，继续迭代。
4. 当cur为NULL时，表示遍历完成，此时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;
    }
};

递归法

递归法通过函数调用自身来实现链表反转。具体步骤如下：

1. 定义递归函数reverse(prev, cur)，其中prev是已反转部分的头节点，cur是当前待反转的节点。
2. 递归结束条件是cur为NULL，此时返回prev。
3. 在每次递归中，将cur->next指向prev，然后调用reverse(cur, newnode)继续递归。

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);
    }
};

三、总结与提炼

链表反转是面试中常见的算法题，掌握多种解法有助于在面试中脱颖而出。建议读者通过画图和实际编码加深理解，熟练掌握这三种方法。