version at : 2022-04-04

/**
1. 反转单链表指定区域
2. 注意null 和 head 的情况
3. 找到l 和 l的前一个节点, r和r的后一个节点, 反转中间的一段并拼接回去
*/
class Solution {
    public ListNode reverseBetween(ListNode head, int l, int r) {
        if (head == null || head.next == null || l == r) return head;

        ListNode prev = new ListNode(-1, head);
        ListNode beforeLeft = prev;
        ListNode right = prev;

        for (int i = 0 ; i<l -1; i++) beforeLeft = beforeLeft.next;
        for (int i = 0 ; i<r; i++) right = right.next;

        ListNode left = beforeLeft.next;
        ListNode afterRight = right.next;

        reverse(left, left.next, afterRight);

        beforeLeft.next = right;
        left.next = afterRight;

        return prev.next;
    }

    public ListNode reverse(ListNode prev, ListNode cur, ListNode end) {
        if (cur == end) return prev;

        ListNode next = cur.next;
        cur.next = prev;

        return reverse(cur, next, end);
    }
}

version at :2020-02-02

/*
1. 翻转中间的一段，需要记录断开处的4个端点，翻转后逆向连接即可
2. 本题需要虚拟前置节点，因为可能需要更新头
3. 链表的变量可以先确定位置，后面就不用再计数遍历了
4. testcase : 链表个数：0，1，2，3，4，5，random
             n，m的差：0，1，2，random
*/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {

        if (head == null || m == n) return head;

        ListNode prev = new ListNode(0);
        prev.next = head;
//         var ph1 = head;
//         var pt1 = head;        

//         for (int i = 1 ; i < m-1; i++) ph1 = ph1.next;
//         for (int i = 1 ; i < n ; i++) pt1 = pt1.next;
        // point-head1 要从prev 开始遍历，因为可能本身就是prev而不是head
        var ph1 = prev;
        var pt1 = prev;        

        for (int i = 0 ; i < m-1; i++) ph1 = ph1.next;
        for (int i = 0 ; i < n ; i++) pt1 = pt1.next;
        var ph2 = ph1.next;
        var pt2 = pt1.next;

        var p1 = ph2;
        var p2 = p1.next;

        while (p1 != pt1){
            var p = p2.next;
            p2.next = p1;

            p1 = p2;
            p2 = p;
        }
        ph1.next = pt1;
        ph2.next = pt2;

        return prev.next;
    }

}