力扣 92.反转链表Ⅱ

力扣《反转链表》系列文章目录

刷题次序，由易到难，一次刷通！！！

一、反转链表Ⅱ

二、解题思路

本题与206.反转链表异曲同工，只需在其基础上考虑将 lefr 至 right 的链表反转后，如何正确连接回原链表上。以下为几个需要注意的点：

1. 考虑 left 为 1 的情况，为实现统一操作，设置一个哨兵节点 dummy node。
   

2. 找到 left 的上一个节点（节点p0），right 的下一个节点。
   

3. 考虑反转全部链表的情况，从原链表的视角看，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}
}