当前位置：首页 > web >正文

nowcoder刷题--反转链表

web 2025/8/26 10:47:30

🎈 个人主页👉：tbRNA-CSDN博客tbRNA-CSDN博客tbRNA-CSDN博客

💯 个人简介：在校大学生一枚💋.
😍 希望我的文章对大家有着不一样的帮助，欢迎大家关注我，感谢大家的多多支持！

🎉 欢迎 👍点赞 ✍评论 ⭐收藏

🦛题目描述

方法一：双链表求解

方法二：递归求解

😪总结

🐐题目链接

🦛题目描述

给定一个单链表的头结点pHead ，长度为n，反转该链表后，返回新链表的表头。

数据范围： 0 ≤ n ≤ 1000

要求：空间复杂度 O(1)，时间复杂度 O(n) 。

如当输入链表 { 1 , 2 , 3 } 时，

经反转后，原链表变为 { 3 , 2 , 1 } ，所以对应的输出为 { 3 , 2 , 1 } 。

以上转换过程如下图所示：

方法一：双链表求解

解题思路：

1️⃣ 首先先把原链表head的下一个节点保存到tmp中。

2️⃣ 摘掉的链表的head节点指向newnode让它成为新的链表的头结点。

3️⃣ newnode = head，head = tmp（注意步骤顺序）

4️⃣ 当原链表遍历完直到head为空时，最后返回新链表的头节点。

class Solution {
public:ListNode* ReverseList(ListNode* head) {ListNode* newHead = nullptr;while(head != nullptr){ListNode* tmp = head->next;head->next = newHead;newHead = head;head = tmp;}return newHead;}
};

方法二：递归求解

首先，我们先对递归函数的定义进行复习

1️⃣ 在C/C++中，递归就是函数⾃⼰调⽤⾃⼰

2️⃣ 递归函数具有以下两个关键特性：

🐘基本情况：这是递归停止的条件。

当问题规模足够小，可以直接解决而不需要进一步分解时，就达到了基本情况。

在C/C++中，基本情况通常是一个简单的返回语句，它不会导致函数再次调用自身。

🐫递归步骤：在这一步中，函数会调用自身，但每次调用时问题的规模都会减小。

递归步骤会包含一个或多个导致函数再次调用自身的条件。

解题思路：

1️⃣ if 判断 是递归停止的条件，当节点为空或节点的下一个节点为空，则返回该节点。

2️⃣ 定义变量ans记录返回的节点。

3️⃣令节点的下一个节点的下一个指向该节点，如果没有这一步代码，ans不能连接剩余返回的节点，只会一直保持 尾节点->NULL （这一步可以打断点调试一下）。

4️⃣设置head节点的下一个节点为空，返回该节点。

class Solution {
public:ListNode* ReverseList(ListNode* head) {if(head == NULL || head->next == NULL){return head;}ListNode* ans = ReverseList(head->next);head->next->next = head;head->next = NULL;return ans;}
};