「LeetCode」92. 反转链表 II
2023-04-18 12:52:59 时间
- 反转链表 II 给你单链表的头指针 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]
提示:
链表中节点数目为 n 1 <= n <= 500 -500 <= Node.val <= 500 1 <= left <= right <= n
进阶: 你可以使用一趟扫描完成反转吗?
思路: 参考反转链表I,在反转链表I基础上我们要注意,当待反转区间的链表反转完成后,我 将待反转区间的前驱节点和后继节点分别连接上待反转区间的链表反转后的头节点与 尾节点。 还有可能操纵头节点,因此需要⼀个虚拟头节点来辅助进⾏操作。
C代码:
/**
* 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* reverseN(ListNode* head, int n) {
if(n == 1) return head;
ListNode *tail = head->next, *p = reverseN(head->next, n - 1);
head->next = tail->next;
tail->next = head;
return p;
}
ListNode* reverseBetween(ListNode* head, int m, int n) {
ListNode ret(0, head), *p = &ret;
int cnt = n - m + 1;
while(--m) p = p->next;
p->next = reverseN(p->next, cnt);
return ret.next;
}
};
java代码:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode hair =new ListNode(-1,head);
ListNode pre = hair, cur =head;
for(int i =0; i<left -1 ; i++){
cur = cur.next;
pre = pre.next;
}
for(int i =0; i< right -left;i++){
ListNode temp =cur.next;
cur.next =cur.next.next;
temp.next =pre.next;
pre.next =temp;
}
return hair.next;
}
}
相关文章
- 运维工程师需要掌握什么技能?有哪些要求?
- 还在惊讶3D打印房子?这个半价的3D打印小区都被抢空了
- 斯坦福开源莫德纳mRNA新冠疫苗的基因测序,在GitHub上
- 互联网24.1%的流量是刷出来的,爬虫被用来作恶,有多可怕?
- 让人更加人性化,让机器有触觉!4 位电子皮肤大牛最新成果盘点
- 2020年全球数据中心基础设施收入1650亿美元
- 从优秀到卓越:成为DevOps专家的7项软技能
- Facebook创造了两个会交流的神经网络来描述颜色
- 什么样的程序员,在35岁以后,依然被公司抢着要?
- 报告:IT人员薪水上涨,心理问题也随工作量增长
- 为什么现代软件如此复杂
- 金电联行首席科学家曹鸿强受邀出席“人工智能创新应用探索”论坛
- “请给我一个五彩斑斓的黑”,只需一行命令就能让AI画画
- MIT研究发现:十大最常用数据集标签错误率达3.4%
- 我,37岁程序员,大把公司抢着要!
- 软件开发10年学会的一些东西
- 以科技引领高质量招聘,北森“2021招聘科技趋势峰会”圆满落幕
- 做垂直场景语音交互专家,声瀚亮相海尔三翼鸟联盟大会
- 刷题太遭罪怎么办?这个算法基地专为小白量身打造,还带动画
- 实现图深度学习复杂研究性质任务太头疼?这个新工具包帮你应对