网站建设费用预算表、,网络运维工程师工资,wordpress 七牛视频教程,国网电子商务平台官网题目描述#xff1a;
给你单链表的头指针 head 和两个整数 left 和 right #xff0c;其中 left right 。请你反转从位置 left 到位置 right 的链表节点#xff0c;返回 反转后的链表 。 示例 1#xff1a; 输入#xff1a;head [1,2,3,4,5], left 2, right 4
输…题目描述
给你单链表的头指针 head 和两个整数 left 和 right 其中 left right 。请你反转从位置 left 到位置 right 的链表节点返回 反转后的链表 。 示例 1 输入head [1,2,3,4,5], left 2, right 4
输出[1,4,3,2,5]示例 2
输入head [5], left 1, right 1
输出[5]提示
链表中节点数目为 n1 n 500-500 Node.val 5001 left right n 进阶 你可以使用一趟扫描完成反转吗
通过次数
445.9K
提交次数
799K
通过率
55.8%
思路和题解
遍历链表p指向正在遍历的节点cur指向前一节点并用一个i记录遍历节点的个数当i在[left,right]之中时cur停止后移用tail指向p表示第一个翻转的节点随后用前插法使p节点插入cur的后面直到iright1随后tail指向p表示反转部分与剩余部分连接。
代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseBetween(ListNode* head, int left, int right) {ListNode* cur,*Head;curHeadnew ListNode;Head-nexthead;ListNode *phead;int i1;while(pileft){pp-next;curcur-next;i;}cur-nextNULL;ListNode *tailp;//记住头插的第一个//开始头插while(piright){ListNode *tp-next;p-nextcur-next;cur-nextp;pt;i;}//(right,end)连上tail-nextp;return Head-next;}
};
