2021-03-19 Leetcode-92

反转链表 II

思路：遍历链表，使在反转范围内的节点依次插入到反转范围的最头部，最终实现反转。
方法：

1. 创立空头节点，链接head（当head也在反转范围中时会用到）
2. 维护以下节点：
   2.1 节点a：left所在节点的前一节点
   2.2 节点start：始终作为反转范围中的第一个节点
   2.3 节点fir：初始反转范围的第一个节点，在遍历过程中不断指向向前插入的节点change的next节点
   2.4 节点cur：遍历游标
   2.5 节点change：需要交换的节点
3. 维护以下变量：
   3.1 count：根据遍历累加，用于比较left，right
4. 流程：
   4.1 从空头结点开始遍历
   4.2 当遍历到left前一节点，赋给a，并同时获取left节点赋给start，fir
   4.3 遍历到left+1节点，把cur赋给change，将change节点插入到a后
   4.4 与此同时，始终保持fir节点的next节点是change的next节点。start节点始终是a节点的next节点，即反转范围的第一个节点。
5. 当遍历完成进行返回：
   5.1 若反转范围包括原先的head节点，则空头节点派上用场，为反转范围的前一节点a，返回a.next即为结果。
   5.2 若反转范围不包括head，则返回head即可。

/**
 * 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) {
        if(head == null) return null;
        ListNode a = null;
        ListNode start = null;
        ListNode fir  = null;
        ListNode nullhead = new ListNode();
        nullhead.next = head;
        ListNode cur = nullhead;
        int count = -1;
        while(cur != null || cur == nullhead){
            count++;
            if(count == left - 1){
                a = cur;
                start = a.next;
                fir = start;
            }
            if(count > left && count < right + 1){
                ListNode change = cur;
                cur = cur.next;
                a.next = change;
                fir.next = change.next;
                change.next = start;
                start = a.next;
                continue;
            }
            cur = cur.next;
        }
        if(left == 1)   return a.next;
        return head;
    }
    
}