【数据结构】【线性表】【练习】反转链表
申明
该题源自力扣题库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;
};题目相关信息到此为止，我们一切来分析一下题目：
- 首先确认链表类型：无头结点的单链表
- 题目目的：反转链表中的某一段链表，反转就是将从头到尾数变成从尾到头数
- 链表可以分为两个部分，反转部分和保持部分
如果我们把链表想象成链条，要我们把链条某一部分反过来我们会怎么做？我相信大部分人都是先将要反转的这一部分从整个链条中拆下来，然后反过来，最后接回去即可。类似的这个题目也可以用这种方法去做。
解题思路
- 找到需要反转部分的链表，并记录链表左侧和右侧
- 将该部分链表进行反转
- 将反转好的链表接回去
思路图解
1.找出需要反转部分的链表，断开链表
2.反转链表
3.接回反转的链表
这里有一个很重要的就是链表的反转，如图所示反转链表只需要改变指针方向即可实现，但因为单链表的不可逆性会造成很大麻烦。
例如这里我需要将2->3改为2->NULL，假定当前遍历指针p指向2
如果我直接写下p->next=NULL：
观察链表发现链表已经断开，无法继续遍历链表。有聪明的同学已经想到，那么我加一个指针cur，在p改变next之前，cur先行一步，到达下一个结点，等p改完next再跟上cur不就可以了？
确实也是如此，我们按这种思路继续往下走，
先行一步：
改变p的next
令p=cur跟上
然后重复操作；但仔细观察会发现， p此时要再更改next已经找不到前驱结点了，第一个结点没前驱结点所以可以直接令p->next=NULL，但第二个结点开始就不可以了。
那么有小伙伴可能也想到了，那我加一个指针pre跟在p后面，一直指向p的前驱结点不将可以了嘛，每次改为p和next，p离开之前pre跟上p，使得p在改next时均指向p的前驱结点：
cur先行一步
p修改next：p->next=pre
pre跟上p
p跟上cur
cur先行一步
修改p的next：p->next=pre
到此链表反转已经完成，rehead从原来指向第一个结点变为指向最后一个结点
这里还有一个需要注意的点是链表的断开与重连，这里思考一下，重连需要几个结点指针？
我们看一下：
原来的1和2断开，3和4断开，反转完成之后1和3相连，2和4相连。因此我们要记录4个结点。
代码解析
/*链表反转代码*/
void reverseLinkedList(struct ListNode* head) {
struct ListNode* pre = NULL;//前驱指针--修改指针的next指向的结点
struct ListNode* cur = head;//修改指针--指向要被修改next的结点
struct ListNode* p = NULL;//遍历指针--遍历整个链表
while (cur != NULL) {//要被修改的结点存在
p= cur->next;//遍历指针向下走一位，为下一个结点反转做准备
cur->next = pre;//将该结点的next指向其前驱结点
pre = cur;//前驱指针跟上修改指针
cur = p;//修改指针跟上遍历指针
}
}
struct ListNode* reverseBetween(struct ListNode* head, int left, int right) {
/*为了方便操作，我们创建一个虚拟头结点*/
struct ListNode dummy;
dummy.next = head;
struct ListNode* prev = &dummy; // prev表示当前结点
struct ListNode* rehead = NULL;//需要反转的链表第一个结点
struct ListNode* pre = NULL;//需要反转部分链表的前驱结点
struct ListNode* curr = NULL;//需要反转部分链表的后继结点
/*遍历链表，将需要反转部分的链表从原链表中剪出来，并记录left-1和right+1两个结点*/
int length = 0;
while (prev->next != NULL && length < right) {//下一结点不为空且链表当前位序小于right
++length;//链表当前位序+1
if (length == left) {//链表当前位序=left
pre = prev;//记录第left-1位结点
rehead = prev->next;//初始化新链表第一个结点，prev指向left
}
prev = prev->next;//当前结点向下移动一位
}
/*循环结束prev指向right*/
pre->next = NULL;//断开链表左侧
curr = prev->next;//记录right+1个结点
prev->next = NULL;//断开链表右侧
reverseLinkedList(rehead);//反转新链表
pre->next = prev;//新链表左侧接回
rehead->next = curr;//新链表右侧接回
return dummy.next;
}