反转链表Ⅱ

92. 反转链表 II

给你单链表的头指针 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]

提示：

• 链表中节点数目为 n
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

进阶： 你可以使用一趟扫描完成反转吗？

找到left的前一个结点pre

找到right的后一个结点nextStart，right.next = null

翻转[left , right]

left.next = nextStart

pre.next指向翻转后的链表

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode p = dummy;
        ListNode start;
        ListNode end;
        //找到left前面的节点
        while(left != 1 && p != null){
            left --;
            right --;
            p = p.next;
        }
        ListNode pre = p;
        start = pre.next;
        while(right != 0 && p != null){
            right --;
            p = p.next;
        }
        ListNode nextStart = p.next;
        p.next = null;
        pre.next = reverseList(start);
        start.next = nextStart;
        return dummy.next;
    }

    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {// 头节点为空或只有一个节点，直接返回
            return head;
        }
        ListNode pre = null;
        ListNode cur = head;
        ListNode temp = null; // 保证遍历不断链
        while (cur != null) {
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        head = pre;
        return head;
    }
}