题意：反转链表的[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;
}
}