qidao123.com技术社区-IT企服评测·应用市场

标题: 反转链表的三种方法--面试必考（图例超具体剖析，小白一看就会！！！） [打印本页]

---

作者: 用户国营    时间: 2025-5-7 20:10
标题: 反转链表的三种方法--面试必考（图例超具体剖析，小白一看就会！！！）
目次
一、前言
二、题目形貌 
三、解题方法
 ⭐ 头插法 --- 创建新的链表
 ⭐ 迭代法 --- 三指针
 ⭐ 递归法
四、总结与提炼
五、共勉

---

一、前言

          反转链表这道题，可以说是--链表专题--，最经典的一道题，也是在面试中频率最高的一道题目，通常在面试中，面试官可能会要求我们写出多种解法来实现这道题目，所以大家需要对这道题目非常熟悉哦！！
      本片博客就来具体的讲讲解一下 反转链表的多种实现方法，让我们的面试变的更加顺利！！！
  二、题目形貌 

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

 三、解题方法

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

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

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

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

复制代码

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

1. // 用于保存下一个节点地址
2. struct ListNode* newnode = cur->next;
3. // 头插
4. cur->next = rphead;
5. rphead = cur;
6. cur = newnode;

复制代码

•  继续同样的操作
  

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

 完整代码：

1. struct ListNode* reverseList(struct ListNode* head)
2. {
3.     // 重新创建一个链表，将之前的链表进行头插即可
4.     struct ListNode* rphead = nullptr;
5.     // 进行指针变换
6.     struct ListNode* cur = head;
7.     while(cur!=NULL)
8.     {
9.         // 用于保存下一个节点地址
10.         struct ListNode* newnode = cur->next;
11.         // 头插
12.        cur->next = rphead;
13.        rphead = cur;
14.        cur = newnode;
15.     }
16.     return rphead;
17. }

复制代码

 ⭐ 迭代法 --- 三指针

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

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

1. ListNode* prev = nullptr;
2. ListNode* cur = head;
3. ListNode* nextNode = cur->next;

复制代码

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

• 接着就是进行的一个迭代操作，首先将【cur】当前的值给到【prev】，然后将【nextnode】当前的值给到【cur】，然后让【nextnode】继续向下，这个时候其实就进行了一个迭代的操作
  
• 1. cur->next = prev;
  2. prev = cur;
  3. cur = nextnode;

  复制代码
• 
  
  

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

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

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

 完整代码：

1. class Solution {
2. public:
3.     ListNode* reverseList(ListNode* head)
4.     {
5.         // 1. 迭代法
7.         // 定义三个指针
8.         ListNode* prev = nullptr;      // cur 的前一个节点
9.         ListNode* cur = head;
10.         // 开始迭代
11.         while(cur!=nullptr)
12.         {
13.             ListNode* nextnode = cur->next;  // cur的下一个指针
14.             cur->next = prev;
15.             prev = cur;
16.             cur = nextnode;
17.         }
18.         return prev;
19.     }
20. };

复制代码

 ⭐ 递归法

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

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

1. class Solution {
2. public:
3.     ListNode* reverse(ListNode* prev, ListNode* cur)
4.     {
5.         // 最终结束条件
6.         if(cur==nullptr)
7.         {
8.             return prev;
9.         }
10.         ListNode* newnode =cur->next;
11.         cur->next = prev;
12.         // 将 cur 作为 prev 传入下一层
13.         // 将 newnode 作为 cur 传入下一层，改变其指针指向当前 cur
14.         return reverse(cur,newnode);
15.     }
16.     ListNode* reverseList(ListNode* head)
17.     {
18.         // 3. 递归法
19.         return reverse(nullptr,head);
20.     }
21. };

复制代码

 四、总结与提炼

            最后我们来总结一下本文所介绍的内容，本文讲解来一道力扣中有关链表翻转的题目，这道题目是校招笔试面试中有关链表章节非常高频的一道题目，大家下去肯定要自己再画画图，分析一下，把这段代码逻辑自己实现一遍，才气更好地掌握
   五、共勉

       以下就是我对 反转链表 的理解，如果有不懂和发现题目的小同伴，请在批评区说出来哦，同时我还会继续更新对 链表专题 的理解，请持续关注我哦！！！    

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 qidao123.com技术社区-IT企服评测·应用市场 (https://dis.qidao123.com/)

Powered by Discuz! X3.4