206. 反转链表
3 min
题目
解法：递归反转
思路
核心思想是使用递归方法从链表尾部开始反转节点指向。递归到链表末尾后，回溯时逐层反转相邻节点的指针方向。正确性在于：递归确保先处理尾部节点，回溯时修改指针不会破坏未处理部分，且每个节点都被精确反转一次。
- Step 1: 递归终止条件：当前节点为空或下一个节点为空时，返回当前节点作为新头节点
- Step 2: 递归调用reverseList(head->next)获取反转后的新头节点
- Step 3: 将当前节点的下一节点指向自身（head->next->next = head）
- Step 4: 断开当前节点的原指向（head->next = NULL）
- Step 5: 返回新头节点
复杂度
- 时间复杂度: ，递归遍历所有节点，每个节点处理一次。
- 空间复杂度: ，递归调用栈深度与链表长度成正比。
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head == NULL || head->next == NULL) return head;
ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return newHead;
}
};