申明
该题源自力扣题库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;//链表当前位序+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;
}