prev/cur/next 三指针逐节点反转，同时保留后续节点引用。
OJ: leetcodecn
题目 ID: reverse-linked-list
难度:入门
标签:链表递归cpppython
日期: 2026-07-28 22:05
题意
反转单链表。
思路
迭代：用 prev 和 cur 两个指针，每次保存 cur->next 后反转指向。递归：head->next 后的链表已反转，将 head 接到末尾。
代码
cpp
/**
* Author by Rainboy
*/
// main.cpp：三指针迭代反转 O(n) O(1)。
#include <bits/stdc++.h>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
ListNode *reverseList(ListNode *head) {
ListNode *prev = nullptr, *cur = head;
while (cur) {
auto next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
};
ListNode *build(istream &in, int n) {
if (!n)
return nullptr;
auto head = new ListNode(0), cur = head;
for (int i = 0, v; i < n; i++) {
in >> v;
cur->next = new ListNode(v);
cur = cur->next;
}
return head->next;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
auto head = build(cin, n);
head = Solution().reverseList(head);
for (auto p = head; p; p = p->next)
cout << p->val << ' ';
return 0;
}python
#!/usr/bin/env python3
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
prev, cur = None, head
while cur:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
return prev
def build(arr):
dummy = cur = ListNode(0)
for v in arr:
cur.next = ListNode(v)
cur = cur.next
return dummy.next
def main() -> None:
n = int(input())
a = list(map(int, input().split()))
head = build(a)
head = Solution().reverseList(head)
while head:
print(head.val, end=" ")
head = head.next
if __name__ == "__main__":
main()复杂度
- 时间复杂度：O(n)。
- 空间复杂度：O(1) 迭代，O(n) 递归栈。
总结
反转链表是链表操作的基本功。迭代三指针是基础版本，递归反转的核心在于"相信子问题已被解决"。