题目描述
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例：
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
思路
1.使用迭代+递归的思想求解。
2.首先为了方便迭代，最好添加一个亚结点在头部，迭代到m的前一个结点pre。
3.然后按照206.反转链表的思路反转部分链表。
4.最后将pre的next指向反转后的头结点即可。
Java代码实现
public ListNode reverseBetween(ListNode head, int m, int n) {
if(m == n)
return head;
int dis = n - m;
ListNode p = new ListNode(-1);
p.next = head;
ListNode res = p;
while(m > 1){
p = p.next;
m--;
}
p.next = reverseNode(p.next,dis);
return res.next;
}
private ListNode reverseNode(ListNode head, int dis){
if(dis == 0 || head == null || head.next == null)
return head;
ListNode p = reverseNode(head.next,dis-1);
ListNode next = head.next.next;
head.next.next = head;
head.next = next;
return p;
}
