网站建设对接流程,制作短视频最好的软件,建筑工程网格化管理台账表格,小企业网站服务器作者#xff1a;小卢 专栏#xff1a;《Leetcode》 喜欢的话#xff1a;世间因为少年的挺身而出#xff0c;而更加瑰丽。 ——《人民日报》 BM1 反转链表
描述#xff1a;
给定一个单链表的头结点pHead(该头节点是有值的#xff0c;… 作者小卢 专栏《Leetcode》 喜欢的话世间因为少年的挺身而出而更加瑰丽。 ——《人民日报》 BM1 反转链表
描述
给定一个单链表的头结点pHead(该头节点是有值的比如在下图它的val是1)长度为n反转该链表后返回新链表的表头。
数据范围0≤n≤1000
要求空间复杂度 O(1) 时间复杂度O(n) 。
如当输入链表{1,2,3}时
经反转后原链表变为{3,2,1}所以对应的输出为{3,2,1}。
以上转换过程如下图所示 示例 思路
初始化3个指针 1pre指针指向已经反转好的链表的最后一个节点最开始没有反转所以指向nullptr 2cur指针指向待反转链表的第一个节点最开始第一个节点待反转所以指向head 3nex指针指向待反转链表的第二个节点目的是保存链表因为cur改变指向后后面的链表则失效了所以需要保存 接下来循环执行以下三个操作 1nex cur-next, 保存作用 2cur-next pre 未反转链表的第一个节点的下个指针指向已反转链表的最后一个节点 3pre cur cur nex; 指针后移操作下一个未反转链表的第一个节点 循环条件当然是cur ! nullptr 循环结束后cur当然为nullptr所以返回pre即为反转后的头结点
代码
struct ListNode* ReverseList(struct ListNode* pHead ) {// write code herestruct ListNode*prepNULL;struct ListNode*cur1pHead;struct ListNode*cur2;while(cur1){cur2cur1-next;cur1-nextprep;prepcur1;cur1cur2;}return prep;
}
NC21 链表内指定区间反转
链表内指定区间反转_牛客题霸_牛客网
题目描述
描述
将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转要求时间复杂度 O(n)空间复杂度 O(1)。 例如 给出的链表为 1→2→3→4→5→NULL, m2,n4, 返回1→4→3→2→5→NULL.
数据范围 0size≤10000m≤n≤size链表中每个节点的值满足∣val∣≤1000
要求时间复杂度 O(n) 空间复杂度O(n)
进阶时间复杂度 O(n)空间复杂度 O(1)
示例1 思路
先找到m的位置然后从进行翻转就可以看我注释
step 1我们可以在链表前加一个表头后续返回时去掉就好了因为如果要从链表头的位置开始反转在多了一个表头的情况下就能保证第一个节点永远不会反转不会到后面去。step 2使用两个指针一个指向当前节点一个指向前序节点。step 3依次遍历链表到第m个的位置。step 4对于从m到n这些个位置的节点依次断掉指向后续的指针反转指针方向。step 5返回时去掉我们添加的表头。
代码
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {// write code herestruct ListNode*newhead(struct ListNode*)malloc(sizeof(struct ListNode));newhead-nexthead;struct ListNode*cur1head;struct ListNode*prepnewhead;for(int i1;im;i){//找到m的位置cur1cur1-next;prepprep-next;}for(int im;in;i){struct ListNode* cur2cur1-next;cur1-nextcur2-next;//防止找不到cur2后面的那个节点cur2-nextprep-next;//cur2一定在翻转部分的最前面。//翻转后在前面的节点一定在prep的后一个节点prep-nextcur2;}return newhead-next;
}
