Note:

先找到left的前面一个node和right node，断开要反转的nodes的最后一个node和他后面node的连接，翻转需要翻转的部分，把翻转的部分接回去

Key word:

partially reverse linked list

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null || head.next == null || left == right) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
    
        //找到left node前的node
        ListNode leftPrev = dummy;
        for (int i = 1; i < left; i++) {
            leftPrev = leftPrev.next;
        }

        ListNode leftNode = leftPrev.next;
        
        //找到right node后的node
        ListNode rightNode = leftPrev;
        for (int i = 0; i <= right - left; i++) {
            rightNode = rightNode.next;
        }
        //断开该断开的部分
        ListNode rightNext = rightNode.next;
        rightNode.next = null;

        // 翻转第二部分
        ListNode partHead = reverse(leftNode);
        
        // merge 
        leftPrev.next = partHead;
        leftNode.next = rightNext;
        return dummy.next;
    }

    private ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}

Complexity Analysis:

TC: O(N);

SC: O(1);