leetcode206-----反转链表

一、题目介绍

二、解题思路

2.1 头插法【建议链表有虚拟头节点】

2.1.1 思路

2.1.2 代码

时间复杂度分析：

空间复杂度分析：

总结：

2.2 改变链表 next 指针的指向【不建议链表有虚拟头节点】

2.2.1 双指针法【不建议链表有虚拟头节点】

时间复杂度分析：

空间复杂度分析：

总结：

2.2.2 第一种递归法【适用于链表中不带虚拟头节点】

时间复杂度分析：

空间复杂度分析：

总结：

2.2.3 方法4（第二种递归写法）

思路：

时间复杂度分析：

空间复杂度分析：

一、题目介绍

题目链接：206. 反转链表 - 力扣（LeetCode）

题意：反转一个单链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

二、解题思路

2.1 头插法【建议链表有虚拟头节点】

2.1.1 思路

头插法实现链表翻转的思路是通过遍历原链表，将每个节点依次插入到新链表的头部，从而实现链表元素的逆序排列。

我们来看看头插法的处理流程：

然后准备进入while循环，ptr指针不为nullptr，因此进入while循环，进入之后，有如下操作：

执行完第一次while循环之后，ptr指向node2，不为nullptr，因此进入第二轮while循环。

进入第三次while循环，如下所示：

第三次while循环执行完成后，ptr为nullptr，不进入第四次while循环，接下来返回新链表的虚拟头节点即可。

这种方法通过创建一个新链表并使用头插法实现链表翻转，但需要额外分配内存，导致空间浪费。

2.1.2 代码

#include<iostream>// 翻转单链表
struct LinkNode{int data; // 定义链表的数据域LinkNode* next; // 定义链表的指针域LinkNode(int x):data(x),next(nullptr){} // 链表节点的构造函数
};// 头插法实现链表翻转
LinkNode* reverseList_addHead(LinkNode* virtualHead){// 首先判断链表if(virtualHead==nullptr){ // 如果链表的虚拟头节点为空，则返回 nullptrreturn nullptr;}if(virtualHead->next==nullptr){ // 如果链表为空，则直接返回链表的虚拟头节点return virtualHead;}// virtualHead 表示旧链表的虚拟头节点// NewListVirtualHead 表示新链表的虚拟头节点LinkNode* NewListVirtualHead = new LinkNode(0); // 定义新链表的虚拟头节点LinkNode* ptr = virtualHead->next; // 定义旧链表的遍历指针 while(ptr!=nullptr){LinkNode* tmp = ptr; // 定义临时指向插入节点的指针  ptr = ptr->next;// 旧链表中移动到下一个节点tmp->next = NewListVirtualHead->next;// 将当前节点插入到新链表头部NewListVirtualHead->next = tmp; // 更新新链表头部}return NewListVirtualHead; // 返回新链表的虚拟头节点//delete NewListVirtualHead;//delete命令只是释放了NewListVirtualHead指针原本所指的那部分内存，//被delete后的指针NewListVirtualHead的值（地址）并非就是NULL，而是随机值。也就是被delete后，//如果不再加上一句NewListVirtualHead=nullptr,NewListVirtualHead会成为乱指的野指针//如果之后的程序不小心使用了NewListVirtualHead，会指向难以预想的内存空间//NewListVirtualHead=nullptr; // 防止野指针
}// 打印链表中所有的元素
void PrintList(LinkNode* VirtualHead){LinkNode* ptr = VirtualHead;while(ptr->next!=nullptr){std::cout<<ptr->next->data<<" ";ptr=ptr->next;}std::cout<<std::endl;
}int main(){LinkNode* virtualHead = new LinkNode(0);  // 创建一个虚拟头节点// 链表为：0--1--2--3--4，0表示虚拟头节点virtualHead->next = new LinkNode(1);virtualHead->next->next = new LinkNode(2);virtualHead->next->next->next = new LinkNode(3);virtualHead->next->next->next->next = new LinkNode(4);virtualHead->next->next->next->next->next = new LinkNode(5);PrintList(virtualHead); // 打印翻转前的链表LinkNode* ReverseListHead = reverseList_addHead(virtualHead); // 链表反转PrintList(ReverseListHead);// 打印翻转后的链表
}

时间复杂度分析：

遍历旧链表：
- 在 while 循环中，我们遍历了整个旧链表。每次循环我们处理一个节点，移动到下一个节点。
- 因此，对于每个节点，操作都是常数时间的，整体遍历链表的时间复杂度是 O(n)，其中 n 是链表中节点的个数。
插入新链表的头部：
- 在每次循环中，执行了常数时间的操作：更新指针 tmp->next = NewListVirtualHead->next 和 NewListVirtualHead->next = tmp。
- 这些操作的时间复杂度为 O(1)，并不会影响整体复杂度。

因此，总体时间复杂度是 O(n)，因为我们仅遍历了链表一次。

空间复杂度分析：

新链表的虚拟头节点：
- 我们创建了一个新的虚拟头节点 NewListVirtualHead。这占用了常数空间 O(1)。
临时指针：
- 我们使用了 ptr 和 tmp 两个指针来遍历和插入节点，这些指针的空间复杂度是 O(1)。
链表节点的重新排列：
- 实际上，原链表中的节点并没有被复制或重新分配内存。只是通过改变指针来实现链表的翻转，因此不需要额外的空间来存储新节点。

因此，空间复杂度是 O(1)，因为除了固定数量的指针外，我们并没有使用任何额外的空间来存储节点。

总结：

时间复杂度：O(n)，我们需要遍历整个链表一次，每个节点处理的时间是常数级别。
空间复杂度：O(1)，除了固定数量的指针外，没有额外的空间开销。

2.2 改变链表 next 指针的指向【不建议链表有虚拟头节点】

在2.1节的方法中，若重新定义一个新的链表来实现元素反转，其实会浪费额外的内存空间。实际上，只需调整链表节点的 next 指针即可直接反转链表，无需额外创建新链表，如图所示。

在链表反转过程中，原头节点是元素1，反转后头节点变为元素5。实际上，我们并没有添加或删除节点，只是调整了 next 指针的方向。

具体步骤如下：

首先，定义一个 cur 指针指向头节点，同时定义一个 pre 指针并初始化为 null。

接下来，开始反转操作。首先，用 tmp 指针保存 cur->next 节点，因为接下来我们需要改变 cur->next 的指向。将 cur->next 指向 pre，此时已完成第一个节点的反转。

然后，进入循环，依次移动 pre 和 cur 指针，直到 cur 指向 null，即遍历完所有节点。此时链表反转完成，返回 pre 指针，它指向新的头节点。

2.2.1 双指针法【不建议链表有虚拟头节点】

代码

// 方法2：改变链表的next指针的指向实现链表翻转【不建议链表有虚拟头节点】
LinkNode* INreverseList(LinkNode* Head){// Head 是链表的头节点，即第一个有效节点LinkNode* curr = Head; // 定义curr指针，指向当前待翻转的节点LinkNode* per = nullptr; //  定义per指针，当前待翻转的节点的前一个节点LinkNode* tmp; // 保存待翻转的节点的后一个节点while(curr!=nullptr){tmp = curr->next;curr->next = per;per = curr;curr = tmp;}return per;
}

时间复杂度分析：

这段代码的主要操作是遍历链表一次，其中每个节点都只被访问一次。因此，时间复杂度为：

遍历链表一次：对于每个节点，都会执行常数时间的操作（保存 next 指针，改变指向等）。因此时间复杂度是 O(n)，其中 n 是链表中的节点数。

空间复杂度分析：

在这个实现中，我们仅使用了三个指针变量：

curr：指向当前正在处理的节点。
per：指向当前节点的前一个节点（即翻转后指向的新节点）。
tmp：临时保存当前节点的下一个节点，用于移动 curr。

这些指针变量是常数空间的，不依赖于链表的大小。因此空间复杂度是 O(1)，即常数空间。

总结：

时间复杂度：O(n)，因为遍历链表一次，每个节点的操作是常数时间。
空间复杂度：O(1)，只使用了有限的常量空间来保存指针。

2.2.2 第一种递归法【适用于链表中不带虚拟头节点】

递归法相对抽象一些，但是其实和双指针法是一样的逻辑，同样是当cur为空的时候循环结束，不断将cur 指向 per 的过程。

关键是初始化的地方，可能有的同学会不理解，可以看到双指针法中初始化 cur = head，per = nullptr，在递归法中可以从如下代码看出初始化的逻辑也是一样的，只不过写法变了。

具体可以看代码（已经详细注释），双指针法写出来之后，理解如下递归写法就不难了，代码逻辑都是一样的。

// 方法3：递归法
LinkNode* Reverse(LinkNode* per, LinkNode* curr){if(curr == nullptr){// 当 curr == nullptr 时，表示递归到达了链表的末尾，返回当前的 per，即翻转后的链表头节点。return per;}LinkNode* tmp = curr->next; // 保存待翻转的节点的后一个节点curr->next=per;return Reverse(curr,tmp);}
LinkNode* ReverseListRecursion(LinkNode* head){return Reverse(nullptr,head);
}

时间复杂度分析：

递归遍历链表：
- 每次递归都处理一个节点。假设链表中有 n 个节点，那么递归将会进行 n 次。
- 每次递归调用的操作都是常数时间 O(1)，包括指针的修改和递归的调用。
因此，递归函数会遍历链表的每个节点一次，总的时间复杂度是 O(n)，其中 n 是链表的节点数。

空间复杂度分析：

递归栈空间：
- 递归调用时，每一次递归调用都会占用栈空间，栈的深度等于递归的次数。
- 每次递归调用会保存当前函数的局部变量，如 per, curr, 和 tmp，这些变量所占用的空间是常数 O(1)。
- 然而，由于递归的深度与链表的长度直接相关，所以递归栈的最大深度是 n，即链表的节点数。
因此，递归方法的空间复杂度是 O(n)，其中 n 是链表的节点数，主要来自于递归栈的空间开销。

总结：

时间复杂度：O(n)，因为每个节点会被访问一次，递归会遍历整个链表。
空间复杂度：O(n)，由于递归栈的深度与链表的长度成正比。

2.2.3 方法4（第二种递归写法）

我们可以发现，上面的递归写法和双指针法实质上都是从前往后翻转指针指向，其实还有另外一种与双指针法不同思路的递归写法：从后往前翻转指针指向。

class Solution {
public:ListNode* reverseList(ListNode* head) {// 边缘条件判断if(head == NULL) return NULL;if (head->next == NULL) return head;// 递归调用，翻转第二个节点开始往后的链表ListNode *last = reverseList(head->next);// 翻转头节点与第二个节点的指向head->next->next = head;// 此时的 head 节点为尾节点，next 需要指向 NULLhead->next = NULL;return last;}
};

这段代码实现了链表的 递归翻转，不过是通过从 尾部开始翻转 的方式来实现的。这种方法与前面讨论的递归方法不同，它是从链表的末尾向前翻转每个节点。

思路：

该方法的核心思想是通过递归逐步进入链表的尾部，在递归回溯的过程中反转每个节点的指向。

递归终止条件：
- if(head == nullptr) return nullptr;：如果当前链表为空，直接返回 nullptr。这是递归的结束条件之一。
- if(head->next == nullptr) return head;：如果当前节点的 next 是 nullptr，说明这是链表的最后一个节点，直接返回该节点作为新的头节点，结束递归。
递归调用：
- LinkNode* last = Reverse2(head->next);：递归地调用 Reverse2 处理链表的剩余部分（即从第二个节点开始的子链表）。这样做的目的是让递归逐渐深入到链表的尾部，直到到达链表的最后一个节点。
反转过程：
- 通过 head->next->next = head; 将当前节点（head）的 next 指向上一个节点，完成链表的反转。也就是说，递归会把当前节点反转为下一个节点的前驱。
- head->next = nullptr;：由于递归到链表尾部时，head 成为链表的尾节点，尾节点的 next 应该指向 nullptr，标志着链表的结束。
返回反转后的头节点：
- 最终，递归返回链表的新的头节点，即 last。

举例说明递归过程

使用链表 1 -> 2 -> 3 来解释 head->next->next = head; 的具体操作。

初始状态：
head -> 1 -> 2 -> 3
递归步骤解析：

我们将链表从尾到头进行反转，每次递归会把当前节点的 next 指针指向前一个节点，直到链表反转完成。

第一步：递归到最后

递归从 head = 1 开始。首先，递归进入到链表的最后一个节点（head = 3）：
// 第一层递归：head = 1
Reverse2(1) → Reverse2(2) → Reverse2(3)
在最底层递归中，head = 3，head->next == nullptr，此时返回节点 3 作为新的头节点。
// 递归到最深层
if (head->next == nullptr) {return head; // 返回节点 3
}
第二步：反转第一个节点（从 head = 2）

回到第二层递归（head = 2）：
// 递归回溯到第二层：head = 2
// last = 3 由上一层返回
// current node = 2, current node's next = 3
在这一步中，head = 2，head->next = 3，我们执行 head->next->next = head;：
head->next 是 3，所以 head->next->next 就是 3->next，即指向 2。
head->next->next = head; 把 3->next 改为指向 2。

当前链表变为：
1 -> 2 -> 3  =>  1 -> 2 <- 3
接下来执行 head->next = nullptr;，将当前节点 2 的 next 指针设为 nullptr，使得 2 成为新的尾节点。

第三步：反转第一个节点（从 head = 1）

回到第一层递归（head = 1）：
// 递归回溯到第一层：head = 1
// last = 3 由上一层返回
// current node = 1, current node's next = 2
在这一步中，head = 1，head->next = 2，我们执行 head->next->next = head;：
head->next 是 2，所以 head->next->next 就是 2->next，即指向 1。
head->next->next = head; 把 2->next 改为指向 1。

当前链表变为：
1 -> 2 <- 3  =>  1 <- 2 <- 3
接下来执行 head->next = nullptr;，将当前节点 1 的 next 指针设为 nullptr，使得 1 成为新的尾节点。

最终链表：

当递归回溯到 head = 1 时，链表已完全反转。最终链表的结构变为：
3 -> 2 -> 1
总结：

通过递归，我们从尾到头逐个节点反转链表，每次递归处理一个节点：

head->next->next = head; 这行代码把当前节点 head 插入到链表的反转部分。
每次反转时，递归将当前节点的 next 指针指向前一个节点，并将当前节点变为新的尾节点。

整个链表反转的过程如下：

初始链表：1 -> 2 -> 3
第一步递归（head = 3）：返回节点 3
第二步递归（head = 2）：2 -> 3 反转成 3 -> 2
第三步递归（head = 1）：1 -> 2 -> 3 反转成 3 -> 2 -> 1

时间复杂度分析：

每次递归调用都会处理一个节点，递归的深度是链表的长度 n。
每次递归的操作（修改指针）是常数时间 O(1)。

因此，时间复杂度为 O(n)，其中 n 是链表的节点数。

空间复杂度分析：

递归的深度为 n，每次递归调用都会消耗栈空间。因此，递归的空间复杂度是 O(n)，主要来自递归栈的开销。
每次递归函数调用使用的空间（局部变量）是常数时间 O(1)。

因此，空间复杂度为 O(n)，由于递归栈的深度为 n。

时间复杂度: O(n)：每个节点都会被访问一次，递归会遍历整个链表。
空间复杂度: O(n)：由于递归栈的深度与链表的长度成正比。

优化建议：

递归方法对栈的依赖较大，且对于大规模链表可能导致栈溢出。对于较大的链表，建议使用 迭代法 来避免递归栈带来的空间开销。

问题：为什么在递归回溯过程中 head 和 last 会自动退回至各自上一个节点？

在递归的过程中，head 和 last 会退回至上一个节点，是因为递归函数的调用栈的特性。让我们深入分析一下这个问题。

递归函数的执行过程：

递归是通过调用栈进行的，每一次递归都会进入函数的下一层，直到递归的出口条件被满足。每次递归返回时，都会恢复到上一个调用层的状态。

在你提供的递归函数中：
LinkNode* Reverse2(LinkNode* head){if(head==nullptr) return nullptr; // 链表的第一个节点若为nullptr，即直接返回nullptr，因为此时的链表是一个空链表if(head->next==nullptr) return head; // 假设head->next等于nullptr，说明链表只有一个节点，那么直接返回该节点即可// 递归调用，翻转第二个节点开始往后的链表LinkNode* last = Reverse2(head->next);// 翻转头节点与第二个节点的指向head->next->next = head;// 此时的 head 节点为尾节点，next 需要指向 nullptrhead->next = nullptr;return last;
}
递归回溯过程

递归调用：每次递归都在处理链表的下一个节点，直到到达链表的最后一个节点。

比如在链表 1 -> 2 -> 3 中，第一次调用 Reverse2(1)，递归进入 Reverse2(2)，然后进入 Reverse2(3)。
当 head = 3 时，head->next == nullptr，递归结束，返回 head = 3。

递归回溯：当递归到达最深层后，开始逐层返回。递归的“返回”是通过函数栈来实现的，即每次递归的返回都会跳回上一个函数调用的地方。

当 Reverse2(3) 返回时，head = 3 被返回到 Reverse2(2)。
在 Reverse2(2) 中，last 就被赋值为 3（即递归返回的节点），并执行接下来的反转操作。

恢复状态：每层递归返回时，head 和 last 的值会“退回”到上一个调用层的状态。此时：

在 Reverse2(2) 中，head = 2，last = 3。
在 Reverse2(1) 中，head = 1，last = 3。
这就是你看到的 head 和 last 自动回到上一个节点的原因。

关键点：

递归调用栈：每次递归调用会压入栈中，并且会一直“深入”下去，直到递归出口（链表的最后一个节点）为止。在递归返回时，栈会逐层“弹出”，并恢复到上一次递归调用时的状态。

传递的参数：在每次递归时，head 会指向当前递归处理的节点，而 last 在最终会指向反转后的链表的新的头节点。随着递归的回溯，last 被返回给上一个调用，并最终指向整个反转后的链表。

例子解析（1 -> 2 -> 3）：

第一次递归：Reverse2(1) 调用 Reverse2(2)
第二次递归：Reverse2(2) 调用 Reverse2(3)
第三次递归：Reverse2(3) 递归终止，返回 head = 3
回溯阶段：
在 Reverse2(2) 中，last = 3 被返回，head = 2，反转节点 2 和 3，链表变为：3 -> 2。
在 Reverse2(1) 中，last = 3 被返回，head = 1，反转节点 1 和 2，链表变为：3 -> 2 -> 1。

总结：

head 和 last 在递归回溯时“自动退回”至上一个节点，是因为递归函数调用栈的自然退栈过程。在每次递归返回时，head 会指向当前处理的节点，last 在递归的最后会指向翻转后的链表头部。

第二种递归法求解思路流程，假设初始情况如下：

递归调用阶段（三次）

递归调用过程如下所示：

递归调用的深度取决于链表的长度 n，每次递归处理一个节点，直到 head->next == nullptr 时停止。

Reverse2(1) 调用 Reverse2(2)
Reverse2(2) 调用 Reverse2(3)
Reverse2(3) 发现 head->next == nullptr，直接返回 head（即 3）

递归回溯阶段（两次）

递归回溯过程只有两次，如下所示：

递归回溯 指的是 函数调用返回时的执行过程，从最后一个调用返回到最初的调用：

回溯到 Reverse2(2)
- last = 3
- head = 2
- head->next->next = head; → 3 → 2
- head->next = nullptr; → 断开 2 → 3
- 返回 last = 3
回溯到 Reverse2(1)
- last = 3
- head = 1
- head->next->next = head; → 2 → 1
- head->next = nullptr; → 断开 1 → 2
- 返回 last = 3