题目描述

反转从位置 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;
    }