Tags
-
中等
-
递归
-
链表
-
java
题目链接:
92. 反转链表 II
解题思路[截取子链表 + 反转 + 拼接]:
以1->2->3->4->5, m = 2, n=4 为例:
-
【截取】定位到需要反转的头结点2, start=2; 前驱节点为1, pre=1; 需要反转的末位节点为4, last=4; 反转子链表的后驱节点为5, next=5;
-
【反转子链表】需要反转2->3->4的子链表, 通过递归实现
注意: 此步骤反转的是子链表, 所以不能像 206.反转链表 一样, 使用head==null || head.next== null作为递归终止条件, 需要使用子链表长度count来作为终止条件
-
【拼接】重新把 前驱节点(1)-> 反转后的子链表(4->3->2) -> 后驱节点(5) 拼接起来, 返回head即可
实现代码:
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
if(head.next == null){
return head;
}
//1. 拆分
ListNode pre = new ListNode(); //需要反转子链表的前驱节点
pre.next = head; //自定义节点, 用于处理left==1的情况
ListNode start = head; //需要反转的头节点
ListNode last = null; //需要反转的尾节点
ListNode next = null; //需要反转子链表的后驱节点
ListNode curr = head; //遍历的当前位
for(int i = 0; i<right; i++){ //遍历链表, 对各个节点变量赋值
if(i == left-2){ //
pre = curr;
start = curr.next;
}
if(i == right-1){
last = curr;
next = curr.next;
}
curr = curr.next;
}
//2. 反转(回溯)
this.backdate(start, (right-left));
//3. 拼接
pre.next = last;
start.next = next;
return left==1 ? pre.next : head; //判断是否从第一位开始反转
}
//递归反转子链表
public ListNode backdate(ListNode head, int count){
if(count == 0){
return head;
}
ListNode cur = backdate(head.next, count-1);
head.next = null;
cur.next = head;
return head;
}
}