LeetCode 力扣 热题 100道（九）反转链表（C++）

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

方法一：迭代法

/*** 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) {ListNode* prev = nullptr;  // 前一个节点ListNode* curr = head;    // 当前节点while (curr != nullptr) {ListNode* next = curr->next;  // 保存下一个节点curr->next = prev;           // 反转当前节点的指针prev = curr;                 // 移动 prev 到当前节点curr = next;                 // 移动 curr 到下一个节点}return prev;  // 返回新的头节点}
};

算法步骤：

1. 初始化两个指针：
   • prev 指向 nullptr，表示当前节点的前驱。
   • curr 指向链表头节点 head。
2. 遍历链表：
   • 保存当前节点的下一个节点 next。
   • 将当前节点的 next 指向 prev，完成反转。
   • 移动 prev 和 curr 指针到下一个节点。
3. 当 curr 为 nullptr 时，链表已反转，prev 即为新链表的头节点。
4. 返回 prev。

方法二：递归法

class Solution {
public:ListNode* reverseList(ListNode* head) {// 递归终止条件if (head == nullptr || head->next == nullptr) {return head;}// 反转剩余链表ListNode* reversedHead = reverseList(head->next);// 调整当前节点的指针head->next->next = head;head->next = nullptr;return reversedHead;  // 返回新的头节点}
};

算法步骤：

1. 递归终止条件：当前节点为 nullptr 或下一个节点为 nullptr（即到达链表尾部）。
2. 递归反转剩余链表：
   • 让新链表的头节点 reversedHead 指向 head->next 反转后的链表头。
3. 调整指针：
   • 让 head->next->next 指向 head，将当前节点追加到反转链表尾部。
   • 设置 head->next = nullptr，断开当前节点和其余节点的连接。
4. 返回 reversedHead。