力扣《反转链表》系列文章目录
刷题次序，由易到难，一次刷通！！！
| 题目 | 题解 |
|---|---|
| 206. 反转链表 | 反转链表的全部 题解1 |
| 92. 反转链表 II | 反转链表的指定段 |
| 24. 两两交换链表中的节点 | 两个一组反转链表 题解2 |
| 25. K 个一组翻转链表 | K 个一组反转题解3 |
一、反转链表Ⅱ
二、解题思路
本题与206.反转链表异曲同工，只需在其基础上考虑将 lefr 至 right 的链表反转后，如何正确连接回原链表上。以下为几个需要注意的点：
-
考虑 left 为 1 的情况，为实现统一操作，设置一个哨兵节点 dummy node。
-
找到 left 的上一个节点（节点p0），right 的下一个节点。
-
考虑反转全部链表的情况，从原链表的视角看，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}
}
