LeetCode 92 Reverse Linked List Ⅱ 反转链表Ⅱ

题目：给定一个单链表的头节点head，和两个整数（left和right，left<=right），要求反转从位置left 到位置right中间的节点，返回反转后的链表。

示例1：

输入： head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

示例2：

输入：head = [5], left = 1, right = 1
输出：[5]

解题思路：

1）找到反转部分的前一个节点pre，并将它作为起始点进行反转部分的操作，例如left为1，则pre应该为none，整个链表都需要反转。为了防止头节点也需要反转，所以我们需要一个newHead去当head的前置节点。

2）从pre节点开始，将left到right的节点逐个移动到反转部分的头部。以示例1为例，我们需要将节点2，3，4进行反转，1与5不变。所以pre节点为1，开始反转的节点start为2。

        a）第一次变换位置时，我们需要将3移动到pre节点1后面，即将pre节点的下一节点指向3，将3的下一节点指向2，将2节点的下一节点指向4，顺序为 1-》3-》2-》4-》5

        b）第二次变换位置时，将4移动到pre节点1后面，即将pre节点的下一节点指向4，将4的下一节点指向3，将2节点的下一节点指向5，顺序为 1-》4-》3-》2-》5

3）最后将反转部分的尾部与剩余链表连接起来。

代码如下：

/**
 * 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) {
        //如果头节点为空或者只反转1个位置的节点，相当于不反转，直接返回
        if (head == null || left == right) {
            return head;
        }

        new一个newHead，使其作为head的pre节点，用于防止第一个节点也需要反转
        ListNode newHead = new ListNode(0, head);

        ListNode pre = newHead;
    
        //首先找到pre节点
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }

        //start节点为开始反转的第一个节点，也是反转后的最后一个节点
        ListNode start = pre.next;
        
        //then节点为我们循环时需要不断拉取到pre节点后的第一个节点，即反转部分的头节点
        ListNode then = start.next;
        
        //从left开始到right为止，反转这部分链表，将反转部分的右侧节点以此提到pre节点的后面
        for (int i = left; i < right; i++) {
            
            /*  
                第一次循环：
                以解题思路的2.a为例，我们要将链表 1-》2-》3-》4-》5 的3 提取到1和2中间，
                使其顺序变为 1-》3-》2-》4-》5；
                转变前，
                pre = 1，
                start = 2，
                then = 3;
                我们将2的next指向3的next即4，将3的next指向pre的next即2，将pre的next指向2的next即3，并让then走向下一个我们要反转的节点4
                转变后：
                pre = 1；
                start = 2；
                then = 4.

                第二次循环：
                以解题思路的2.b为例，我们要将链表 1-》3-》2-》4-》5 的4 提取到1和3中间，
                使其顺序变为 1-》4-》3-》2-》5；
                转变前，
                pre = 1；
                start = 2；
                then = 4.
                所以将start的next指向then的next即5，将then的next指向pre的next即3，将pre的next指向then即4，然后将then移动到下一个节点5.
            */    
            start.next = then.next;
            then.next = pre.next;
            pre.next = then;
            then = start.next;
        }
        return newHead.next;

    }
}