【数据结构】【线性表】【练习】反转链表

申明

        该题源自力扣题库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. 链表可以分为两个部分，反转部分和保持部分

        如果我们把链表想象成链条，要我们把链条某一部分反过来我们会怎么做？我相信大部分人都是先将要反转的这一部分从整个链条中拆下来，然后反过来，最后接回去即可。类似的这个题目也可以用这种方法去做。

解题思路

1. 找到需要反转部分的链表，并记录链表左侧和右侧
2. 将该部分链表进行反转
3. 将反转好的链表接回去

思路图解

        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;//链表当前位序+1if (length == left) {//链表当前位序=leftpre = 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;
}