网站域名是什么意思,wordpress require,做分析图地图网站,新手机发布申明 该题源自力扣题库19#xff0c;文章内容#xff08;代码#xff0c;图表等#xff09;均原创#xff0c;侵删#xff01;
题目 给你单链表的头指针head以及两个整数left和right#xff0c;其中leftright#xff0c;请你反转从位置left到right的链表节点…申明 该题源自力扣题库19文章内容代码图表等均原创侵删
题目 给你单链表的头指针head以及两个整数left和right其中leftright请你反转从位置left到right的链表节点返回反转后的链表结果
示例 输入[1,2,3,4,5]left2right4
输出[1,4,3,2,5]
链表结构体
struct ListNode {int val;struct ListNode *next;
}; 题目相关信息到此为止我们一切来分析一下题目
首先确认链表类型无头结点的单链表题目目的反转链表中的某一段链表反转就是将从头到尾数变成从尾到头数链表可以分为两个部分反转部分和保持部分 如果我们把链表想象成链条要我们把链条某一部分反过来我们会怎么做我相信大部分人都是先将要反转的这一部分从整个链条中拆下来然后反过来最后接回去即可。类似的这个题目也可以用这种方法去做。
解题思路
找到需要反转部分的链表并记录链表左侧和右侧将该部分链表进行反转将反转好的链表接回去
思路图解 1.找出需要反转部分的链表断开链表 2.反转链表 3.接回反转的链表 这里有一个很重要的就是链表的反转如图所示反转链表只需要改变指针方向即可实现但因为单链表的不可逆性会造成很大麻烦。 例如这里我需要将2-3改为2-NULL假定当前遍历指针p指向2 如果我直接写下p-nextNULL 观察链表发现链表已经断开无法继续遍历链表。有聪明的同学已经想到那么我加一个指针cur在p改变next之前cur先行一步到达下一个结点等p改完next再跟上cur不就可以了 确实也是如此我们按这种思路继续往下走
先行一步 改变p的next 令pcur跟上 然后重复操作但仔细观察会发现 p此时要再更改next已经找不到前驱结点了第一个结点没前驱结点所以可以直接令p-nextNULL但第二个结点开始就不可以了。 那么有小伙伴可能也想到了那我加一个指针pre跟在p后面一直指向p的前驱结点不将可以了嘛每次改为p和nextp离开之前pre跟上p使得p在改next时均指向p的前驱结点 cur先行一步 p修改nextp-nextpre pre跟上p
p跟上cur cur先行一步
修改p的nextp-nextpre 到此链表反转已经完成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和right1两个结点*/int length 0;while (prev-next ! NULL length right) {//下一结点不为空且链表当前位序小于rightlength;//链表当前位序1if (length left) {//链表当前位序leftpre prev;//记录第left-1位结点rehead prev-next;//初始化新链表第一个结点prev指向left}prev prev-next;//当前结点向下移动一位}/*循环结束prev指向right*/pre-next NULL;//断开链表左侧curr prev-next;//记录right1个结点prev-next NULL;//断开链表右侧reverseLinkedList(rehead);//反转新链表pre-next prev;//新链表左侧接回rehead-next curr;//新链表右侧接回return dummy.next;
}
