掌握反转链表的艺术：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->next
cur->next = pre; // 反转指针方向
// 更新pre 和 cur指针
pre = cur;
cur = tmp;
}
return pre; // 返回反转后的头节点
}
};
// 根据一个整数数组创建链表
ListNode* createList(vector<int>& nums) {
ListNode* head = NULL;
ListNode* current = NULL;
for (int i = 0; i < nums.size(); ++i) {
if (head == NULL) {
head = new ListNode(nums[i]);
current = head;
} else {
current->next = new ListNode(nums[i]);
current = current->next;
}
}
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 = val
self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
cur = head
pre = None
while cur:
temp = cur.next # 保存一下 cur 的下一个节点
cur.next = pre # 反转
pre = cur # 更新 pre 和 cur 指针
cur = temp
return pre
def createList(nums):
head = None
tail = None
for num in nums:
if not head:
head = ListNode(num)
tail = head
else:
tail.next = ListNode(num)
tail = tail.next
return head
def printList(head):
cur = head
while cur:
print(cur.val, end=" ")
cur = cur.next
print()
# 主程序
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 pre
temp = cur.next
cur.next = pre
return self.reverse(temp, cur)