html静态网站开发实验,flash中文网站模板,网络游戏公司,怎样同步wordpress力扣《反转链表》系列文章目录
刷题次序#xff0c;由易到难#xff0c;一次刷通#xff01;#xff01;#xff01;
题目题解206. 反转链表反转链表的全部 题解192. 反转链表 II反转链表的指定段24. 两两交换链表中的节点两个一组反转链表 题解225. K 个一组翻转链表K …力扣《反转链表》系列文章目录
刷题次序由易到难一次刷通
题目题解206. 反转链表反转链表的全部 题解192. 反转链表 II反转链表的指定段24. 两两交换链表中的节点两个一组反转链表 题解225. K 个一组翻转链表K 个一组反转题解3
一、反转链表Ⅱ 二、解题思路
本题与206.反转链表异曲同工只需在其基础上考虑将 lefr 至 right 的链表反转后如何正确连接回原链表上。以下为几个需要注意的点 考虑 left 为 1 的情况为实现统一操作设置一个哨兵节点 dummy node。 找到 left 的上一个节点节点p0right 的下一个节点。 考虑反转全部链表的情况从原链表的视角看pre 指向最后一个节点反转后的第一个节点cur 指向空。而对于反转链表中 left 至 right 的情况pre 仍指向最后一个节点反转后的第一个节点而 cur 指向后半部分未反转的第一个节点也就是 right 的下一个节点。将 left 的上一个节点叫做 p0则 p0.next left反转后 left 为这段的最后一个节点需要指向原来 right 的下一个节点cur即需 p0.next 指向 cur之后将 p0.next 指向 反转部分链表的第一个节点即让 p0.next 指向 pre。注意这里两次指向的顺序不能颠倒
三、代码
/*** 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 dummy new ListNode(0, head);ListNode p0 dummy;// 让 p0 指向 left 的上一个节点for (int i 0; i left - 1; i) {p0 p0.next;}ListNode pre null;ListNode cur p0.next;for (int i 0; i right - left 1; i) {ListNode nxt cur.next;cur.next pre;// 反转pre cur;// 更新指针cur nxt;// 更新指针}// 让部分反转的节点正确连接回原来的整个链表p0.next.next cur; p0.next pre;return dummy.next;// 注意不返回哨兵节点 dummy node}
}
