解决反转链表问题

反转链表的迭代方法：

        使用三个指针 n1、n2 和 n3 分别表示前一个节点、当前节点和下一个节点。通过遍历链表，逐个反转节点的指向。

ListNode* reverseList(ListNode* head) {
if (head == nullptr) {
return head;
}

ListNode* n1 = nullptr;
ListNode* n2 = head;
ListNode* n3 = head->next;

while (n2 != nullptr) {
n2->next = n1;
n1 = n2;
n2 = n3;
if (n3 != nullptr) {
n3 = n3->next;
}
}
return n1;
}

初始状态

第一次循环

第二次循环

第三次循环

第四次循环

第五次循环

反转链表的递归方法：

        递归方法通过不断调用自身，将链表从尾部开始反转。每次递归调用处理当前节点的下一个节点，并反转指针方向。

ListNode* reverseList(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}

ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return newHead;
}

代码说明：

• 迭代方法：通过循环逐个反转节点，时间复杂度为 O(n)，空间复杂度为 O(1)。
• 递归方法：利用函数调用栈实现反转，时间复杂度为 O(n)，空间复杂度为 O(n)（递归栈空间）。

        两种方法均能有效反转链表，选择时可根据具体场景决定。