【数据结构】【线性表】【练习】反转链表II
目录
申明
题目
头插法解题
步骤图解
程序解析
申明
该题源自力扣题库19，文章内容（代码，图表等）均原创，侵删！
本文章续写上篇文章的反转链表，让我们回顾一下上篇文章的题目内容：
题目
给你单链表的头指针head以及两个整数left和right，其中left<=right，请你反转从位置left到right的链表节点，返回反转后的链表结果！
示例：
输入：[1,2,3,4,5]，left=2，right=4
输出：[1,4,3,2,5]
链表结构体
struct ListNode {
int val;
struct ListNode *next;
};题目内容到此位置，题目意思应该很好理解，在上篇文章中我们的解题思路主要是选将需要反转的链表拆出来，如何将其反转，最后接回去。虽然功能实现了，但在这个过程中我们也发现过程不是很顺利，一个是需要两次遍历，切链表的时候遍历一次，反转链表的时候遍历一次；其次是因为需要大量指针，为了实现单链表的反转就需要三个指针，为了链表的拆和接也需要四个指针。
头插法解题
如果看过我之前的文章的话或许会发现，其实我在将单链表的建立的时候就提到过反转链表的方法-头插法。当时我们讲到链表的建立有两种方法，一个是头插法，一个是尾插法。头插法即每一个新结点都插入到头结点之后，因此后插的结点会在先插的结点前面实现链表的反转。
类似的，我们也可以用头插法反转链表，首先我们在找到left的前驱结点
然后遍历链表的left-right，如示例，此时我们将结点3插入到1之后（2已经在1之后了，不需要再插了）。这次插入的目标是得到这个
观察上下两幅图，我们需要做的是
- 将1的next指向3
- 将3的next指向2
- 将2的next指向4
这是我们要的效果，但在实际操作中要十分注意你的操作顺序，这里涉及到三个结点，且要对每个结点的next都进行改变，同样的，我们也要用三个指针去操作，我们引入两个新指针start和next
然后我们开始将3，插入到1后面，我们先分析一下next修改的顺序，有顺序的原因是因为自己要修改的next要先给到别人使用，因此我们分析一下这三个结点的next关系：
- 1的next要给3
- 2的next不要了
- 3的next要给2
我们发现2的next没用，因此我们先修改2的next(将3的next给2）;此时3的next已经给过2了，因此接下来就修改3的next(将1的next给3)；最后我们修改1的next，直接指向3.所以我们的修改顺序为：
- 修改2的next，将3的next给2
- 修改3的next，将1的next给3
- 修改1的next，将1的next指向3
用指针来表述就是：
- start->next=then->next;
- then->next=prev->next;
- prev->next=then;
步骤图解
1.修改start的next
2.修改3的next
3.修改1的next
看着是不是很别扭，没事我们跟着箭头把它拉直
拉直之后就是这样了，是不是就插进来了。接下来对后续结点重复相同的步骤即可。
这里需要注意的遍历，不知道你们有没有发现，就在链表的位序而言，start和then位置已经交换了，其实start已经可以视为向前一位了，遍历的时候只需要更改then指向4即可，也就是then=start->next.
程序解析
struct ListNode* reverseBetween(struct ListNode* head, int left, int right) {
// 创建一个虚拟头节点
struct ListNode dummy;
dummy.next = head;
struct ListNode *prev = &dummy;
// 找到第left-1个节点
for (int i = 0; i < left - 1; ++i) {
prev = prev->next;
}
// 开始反转从left到right的部分
struct ListNode *start = prev->next;//初始化start指向left
struct ListNode *then = start->next;//初始化then指向right
for (int i = 0; i < right - left; ++i) {//遍历需要反转部分链表
start->next = then->next;
then->next = prev->next;
prev->next = then;
then = start->next;
}
return dummy.next;
}建议各位在草稿纸上跟着程序结合例题，操作一遍会更加清晰，特别是反转链表那一部分。