LeetCode/92. 反转链表 II

92. 反转链表 II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

以前写过206. 反转链表的题解，本题是该题的升级版，总的来说还是递归的思想。206. 反转链表通过递归，使得head的下个元素的next（即head.next.next）指针指向head，然后断开head的next指针，其实就实现了一个元素的反转，最终头结点指向反转后最后一个结点。

我们思考，如果反转前N个元素应该怎么做，首先肯定需要一个记录终止点的元素，要不然就跟反转整个链表一样。这里可以设置一个ListNode用来标记后继不需要反转的链表的头结点，因为我们反转后head结点指向该链最后一个元素，只要让head.next接上后继链表即可。具体代码如下：

// 反转前N个链表
ListNode successor = null;
private ListNode reverseN(ListNode head, int n) {
  	//如果只需要反转一个结点，不需要反转的链表就是当前结点后继
    if (n == 1) {
        successor = head.next;
        return head;
    }
    
  	//最后last就是反转后链表的头结点
    ListNode last = reverseN(head.next, n - 1);
  	//这个就是反转链表的基操
    head.next.next = head;
    
  	//记得最后反转后head结点指向反转链表的最后一个结点
    head.next = successor;
    return last;
}

对于反转指定区间的元素，我们可以将一般特殊化，其实也是一种变种的反转前N个结点的操作，将head作为第一个元素时，我们反转区间从m开始，如果将head.next作为第一个元素时，反转区间将从m – 1开始，那么总有一个结点，使得我们的m == 1，这时我们套用反转前N个结点的方式进行操作即可。

具体代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
      	//到达反转区间，直接当做反转前N个结点操作即可
        if (m == 1)
            return reverseN(head, n);
        
      	//递归到达满足条件的结点
        head.next = reverseBetween(head.next, m - 1, n - 1);
        return head;
    }
    
    // 反转整个链表
//     private ListNode reverse(ListNode head) {
//         if (head.next == null) 
//             return head;
        
//         ListNode last = reverse(head.next);
//         head.next.next = head;
//         head.next = null;
//         return last;
//     }
    
    // 反转前N个结点的链表
    ListNode successor = null;
    private ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            successor = head.next;
            return head;
        }
        
        ListNode last = reverseN(head.next, n - 1);
        head.next.next = head;
        
        head.next = successor;
        return last;
    }
}