面试经典150题——反转链表 II

1. 题目描述

2.  题目分析与解析

2.1 思路一

首先题目明确是单链表，left和right是两个位置，那么我们就可以知道如果遍历链表，找到某个位置等于left的节点，就说明从这个节点开始需要反转，找到位置等于right的节点，就说明反转截止，把后续节点拼接上就行了。

如何进行翻转？我们来想一下，left到right部分的反转，意味着left位置

原来再该子链表的头，最终会变成尾部，而right作为原始链表的尾部，会变为头节点。

因此我们可以在遍历到left节点时，对于后续每一个节点，将它指向它前一个节点，最后再把后续部分（right后的部分）和前缀（left前面的内容）拼接上就可以得到结果了。

代码思路：

1. 遍历原始链表

2. 寻找left位置

3. 对于后续每一个节点，先取出它的下一个节点存储在temp，然后将当前节点指向它的前一个节点

4. 当走到right，此时temp为后续内容，将前序部分（left前一个节点）的next指向right，将left节点指向temp

5. 返回head

但是在实际解答过程中我发现对于left等于1的情况总会报错，因为我在代码中定义了left之前的一个节点，为了方便后续的拼接用的，但是如果left等于1，那么它就没有前序节点，处理起来就比较复杂。

所以这里的精髓就是提出一个哨兵节点，放在head节点的前面，就可以保证每一个节点都有一个前序节点，避免了过多的判断。

改进后代码思路：

1. 创建一个虚拟头节点

2. ​创建一个节点寻找left节点的前一个节点

3. 创建一个前驱节点与当前需要反转的节点变量

4. 进行反转操作

5. 连接前后节点

6. 返回虚拟头节点的下一个节点，也就是实际的头节点

虚拟节点的主要作用就是防止left为1的情况。

3. 代码实现

4. 相关复杂度分析

时间复杂度：O(n)，其中 n 是链表的长度。算法需要遍历链表一次就可以完成所有操作。

空间复杂度：O(1)，只需要常数级别的额外空间来存储临时变量。