【LeetCode面试经典150题】92. 反转链表 II

一、题目

• 92. 反转链表 II - 力扣（LeetCode）
• 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

二、思路

1. 链表的反转操作实际上就是改变指针的指向，如 A->B->C 变为 A<-B<-C 而不用改变其内部元素；
2. 所以操控链表的反转需要使用三个指针分别标定前驱(pre)、当前(cur)以及后继(nxt)，具体原因如下： 当改变pre与cur的指向时，cur的原下一个结点就无法指定了，所以需要事先指定一个nxt结点；
3. 为了防止传入的链表长度为0，还需要设置dummy结点，以免空指针；
4. 最后只需要连接反转后链表的头尾即可，见解法一；

  A  ->  B  ->  C
  ^      ^      ^
 pre    cur    nxt
 
  A  <-  B      C
  ^      ^      ^
 pre    cur    nxt
 
  A  <-  B  <-  C
  ^      ^      ^
 pre    cur    nxt

三、解法

解法一

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(-1, head), p = dummy;
        for (int i = 0; i < left - 1; i++) {
            // 找到待交换结点的前一个结点
            p = p.next;
        }
 
        ListNode pre = null, cur = p.next;
        for (int i = 0; i < right - left + 1; i++) {
            ListNode nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
 
        p.next.next = cur;
        p.next = pre;
        
        return dummy.next;
    }
}