【反转子链表】模拟题-526互联

题意：反转链表的[left, right]，返回链表表头

题解：直接模拟删除的过程即可

定义重要节点
记录left位置的节点为lnode，right位置的节点为rnode
lnode的前驱节点为pre，right位置的后继节点为suc
初始化pre = suc = lnode = rnode = 原链表表头前的虚拟节点
使节点从虚拟节点走到定义的位置
pre跳l-1次走到自己的位置
lnode再从pre跳1次走到自己的位置
rnode从lnode跳r-l次走到自己的位置
suc从rnode跳1次走到自己的位置
反转[left, right]处的链表
修改pre和lnode的next节点
pre.next = reverse(lnode);
lnode.next = suc;

模拟代码

/**
 * 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 {
    ListNode pre, suc, lnode, rnode;
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(0, head);
        pre = suc = lnode = rnode = dummy;

        int t = left - 1;
        while(t -- > 0) {
            pre = pre.next;
        }
        lnode = pre.next;
        rnode = lnode;
        t = right - left;
        while(t -- > 0) {
            rnode = rnode.next;
        }
        suc = rnode.next;
        pre.next = reverse(lnode);
        lnode.next = suc;
        return dummy.next;
    }
    public ListNode reverse(ListNode head) {
        if(head == rnode) return head;
        ListNode res = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return res;
    }
}