92.反转链表II

/**
 * 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);
      dummy.next = head;
      ListNode pre = dummy;
      // 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
      for(int i = 0;i<left-1;i++){
        pre = pre.next;
      }
      // 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
      ListNode rightNode = pre;
      for(int i = 0;i<right - left + 1;i++){
        rightNode = rightNode.next;
      }

       // 第 3 步：切断出一个子链表（截取链表）
      ListNode leftNode = pre.next;
      ListNode cur = rightNode.next;

      pre.next = null;
      rightNode.next = null;

      // 第 4 步：反转链表的子区间
      reverseLinkedList(leftNode);
      
      // 第 5 步：接回到原来的链表中
      pre.next = rightNode;
      leftNode.next = cur;
      return dummy.next;

    }
    public void reverseLinkedList(ListNode head){
      ListNode pre = null;
      ListNode cur = head;
      while(cur != null){
        ListNode next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
      }
    }
}