掌握反转链表的艺术：LeetCode 206 深入解析与优化 - 双指针与递归方法精讲-拓冰建站

LeetCode.206反转链表

1.问题描述
2.解题思路
3.代码

1.问题描述

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

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

2.解题思路

如果再定义一个新的链表，实现链表元素的反转，其实这是对内存空间的浪费。其实只需要改变链表的next指针的指向，直接将链表反转，而不用重新定义一个新的链表，如图所示:

双指针法（双指针解其他题常见，点击链接跳转即可）
- 定义一个cur指针，指向头结点；再定义一个pre指针，初始化为null。
- 那我们目的是反转链表，也就是让当前头结点指向null，再将头结点的下一个节点，指向头节点。
- 首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。
- 接下来循环逻辑，不断移动pre和cur指针。
- 最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。此时我们return pre指针就可以了，pre指针就指向了新的头结点。
- 时间复杂度: O(n)
- 空间复杂度: O(1)
递归

与双指针法是一样的逻辑，同样是当cur为空的时候循环结束，不断将cur指向pre的过程。
- 时间复杂度: O(n), 要递归处理链表的每个节点
- 空间复杂度: O(n), 递归调用了 n 层栈空间

3.代码

C++:双指针

#include <iostream>
#include <vector>
using namespace std;// 定义链表节点结构
struct ListNode {int val;        // 节点存储的值ListNode* next; // 指向下一个节点的指针ListNode(int x) : val(x), next(NULL) {} // 构造函数
};class Solution {public:ListNode* reverseList(ListNode* head) {ListNode* cur = head; // 当前节点指针ListNode* pre = NULL; // 前一个节点指针ListNode* tmp;        // 临时节点指针while(cur) {tmp = cur->next;  // 保存一下 cur的下一个节点，因为接下来要改变cur->nextcur->next = pre;  // 反转指针方向// 更新pre 和 cur指针pre = cur;        cur = tmp;        }return pre;          // 返回反转后的头节点}
};// 根据一个整数数组创建链表
ListNode* createList(const vector<int>& nums) {ListNode* head = NULL; // 链表头指针ListNode* tail = NULL; // 链表尾指针for (int num : nums) {ListNode* newNode = new ListNode(num); // 创建新节点if (!head) {head = newNode; // 初始化头尾节点为第一个节点tail = newNode;} else {tail->next = newNode; // 在尾部添加新节点tail = newNode;       // 更新尾指针}}return head; // 返回链表头指针
}// 打印链表中的元素
void printList(ListNode* head) {ListNode* cur = head; // 当前节点指针while(cur) {cout << cur->val << " "; // 打印当前节点值cur = cur->next;         // 移动到下一个节点}cout << endl; // 打印换行符
}// 主函数
int main() {vector<int> nums; // 存储用户输入的整数数组int num;          // 用户输入的单个整数// 提示用户输入，以0结束cout << "Enter numbers for the list (0 to end): ";while (cin >> num && num != 0) {nums.push_back(num); // 将输入的数字添加到数组中}// 创建链表ListNode* head = createList(nums);// 打印反转前的链表cout << "Before reverse: ";printList(head);// 创建Solution类实例，并反转链表Solution sol;ListNode* newHead = sol.reverseList(head);// 打印反转后的链表cout << "After reverse: ";printList(newHead);return 0; // 程序正常结束
}

C++:递归

class Solution {
public:ListNode* reverse(ListNode* pre,ListNode* cur){if(cur == NULL) return pre;  //终止条件ListNode* temp = cur->next;cur->next = pre;// 可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步// pre = cur;// cur = temp;return reverse(cur,temp);  //下一层递归，根据上面，把cur赋值给pre，把temp赋值给cur，所以reverse传入的参数，第一个为，cur，第二个为temp，就可以实现递归了}ListNode* reverseList(ListNode* head) {// 和双指针法初始化是一样的逻辑// ListNode* cur = head;// ListNode* pre = NULL;return reverse(NULL, head);}};

python：双指针

class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextclass Solution:def reverseList(self, head: ListNode) -> ListNode:cur = headpre = Nonewhile cur:temp = cur.next  # 保存一下 cur 的下一个节点cur.next = pre  # 反转pre = cur  # 更新 pre 和 cur 指针cur = tempreturn predef createList(nums):head = Nonetail = Nonefor num in nums:if not head:head = ListNode(num)tail = headelse:tail.next = ListNode(num)tail = tail.nextreturn headdef printList(head):cur = headwhile cur:print(cur.val, end=" ")cur = cur.nextprint()# 主程序
if __name__ == "__main__":nums = list(map(int, input("Enter numbers for the list (separated by space): ").split()))head = createList(nums)print("Before reverse:")printList(head)sol = Solution()newHead = sol.reverseList(head)print("After reverse:")printList(newHead)

python: 递归

class Solution:def reverseList(self, head: ListNode) -> ListNode:return self.reverse(head, None)def reverse(self, cur: ListNode, pre: ListNode) -> ListNode:if cur == None:return pretemp = cur.nextcur.next = prereturn self.reverse(temp, cur)