LeetCode - 206. 反转链表

目录

题目

反转链表的详细步骤

反转链表递归实现的详细过程

递归调用栈展开过程

递归调用栈回溯过程

图示演变过程

读者可能出现的错误写法

正确写法

---

题目

206. 反转链表 - 力扣（LeetCode）

反转链表的详细步骤

递归方法步骤

处理边界情况：

• 如果链表为空(head == nullptr)，直接返回nullptr

• 如果链表只有一个节点(head->next == nullptr)，直接返回head

递归反转子链表：

• 调用reverseList(head->next)递归处理除了头节点外的其余部分

• 这会返回反转后子链表的新头节点(newHead)，即原链表的最后一个节点

调整当前节点的连接：

• 将head的下一个节点的next指向head：head->next->next = head

• 这一步将当前节点接到反转后子链表的末尾

断开原有连接：

• 将head的next设为nullptr：head->next = nullptr

• 这样防止链表中形成环

返回新头节点：

• 返回在递归中获得的新头节点newHead

反转链表递归实现的详细过程

假设我们有链表：1 -> 2 -> 3 -> 4 -> 5 -> nullptr

递归调用栈展开过程

调用 reverseList(1)

• 1->next 不为 nullptr，继续递归

• 调用 reverseList(2)

调用 reverseList(2)

• 2->next 不为 nullptr，继续递归

• 调用 reverseList(3)

调用 reverseList(3)

• 3->next 不为 nullptr，继续递归

• 调用 reverseList(4)

调用 reverseList(4)

• 4->next 不为 nullptr，继续递归

• 调用 reverseList(5)

调用 reverseList(5)

• 5->next 为 nullptr，这是基本情况

• 返回 5 作为新的头节点

递归调用栈回溯过程

返回到 reverseList(4)

• newHead = 5

• 执行 4->next->next = 4 (即 5->next = 4)

• 执行 4->next = nullptr

• 此时链表变为：5 -> 4 -> nullptr，3 -> 4 (断开)

• 返回 newHead = 5

返回到 reverseList(3)

• newHead = 5

• 执行 3->next->next = 3 (即 4->next = 3)

• 执行 3->next = nullptr

• 此时链表变为：5 -> 4 -> 3 -> nullptr，2 -> 3 (断开)

• 返回 newHead = 5

返回到 reverseList(2)

• newHead = 5

• 执行 2->next->next = 2 (即 3->next = 2)

• 执行 2->next = nullptr

• 此时链表变为：5 -> 4 -> 3 -> 2 -> nullptr，1 -> 2 (断开)

• 返回 newHead = 5

返回到 reverseList(1)

• newHead = 5

• 执行 1->next->next = 1 (即 2->next = 1)

• 执行 1->next = nullptr

• 此时链表变为：5 -> 4 -> 3 -> 2 -> 1 -> nullptr

• 返回 newHead = 5

最终结果

• 返回 newHead = 5，链表已完全反转

图示演变过程

初始:    1 -> 2 -> 3 -> 4 -> 5 -> nullptr
步骤6:   1 -> 2 -> 3 -> 4    5 -> 4 -> nullptr
步骤7:   1 -> 2 -> 3         5 -> 4 -> 3 -> nullptr
步骤8:   1 -> 2              5 -> 4 -> 3 -> 2 -> nullptr
步骤9:   1                   5 -> 4 -> 3 -> 2 -> 1 -> nullptr

读者可能出现的错误写法

class Solution {
public:ListNode* reverseList(ListNode* head) {if(!head->next){return;}reverseList(ListNode* head->next);head->next->next = head;head -> next = nullptr;}
};

返回值缺失：

• 在第一个if条件中，你使用了return;而没有返回值，但函数需要返回ListNode*

• 递归函数没有返回反转后的新头节点

语法错误：

• reverseList(ListNode* head->next);中不应该再次声明ListNode*类型

边界条件处理不完整：

• 没有处理head为nullptr的情况

正确写法

class Solution {
public:ListNode* reverseList(ListNode* head) {if(head == nullptr){return nullptr;}if(head->next == nullptr){return head;}ListNode* newHead = reverseList(head->next);head->next->next = head;head -> next = nullptr;return newHead;}
};