1、前言

题目描述

2、思路

此题最简单清晰的方法使用双指针。我们定义两个指针，分别称之为g(guard 守卫)和p(point)。g 在要移动的节点的前一个节点，p 在要移动的节点上。然后 p 后面的节点使用头插法，一个个的插入到 g 的后面，完美解决。

但是，最简单的代码却是递归来做。我们首先可以想一下单链表递归反转怎么做，然后递推到单链表递归反转前 n 个节点，最后递推到单链表递归反转 m 到 n 的节点。

单链表递归反转比较简单，主要是递归能记录上一个节点：

    public ListNode reverseListNode(ListNode head){
        if(head.next == null){
            return head;
        }

        ListNode last = reverseListNode(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }

然后我们由反转整个单链表，递推到只返回单链表前 m 个节点，此时我们需要一个 end 指针记录第 m 个节点后一个节点：

    ListNode end = null;

    public ListNode reverseListNodeN(ListNode head, int m){
        if(m == 1){
            end = head.next;
            return head;
        }

        ListNode last = reverseListNodeN(head.next, m - 1);
        head.next.next = head;
        head.next = end;
        return last;
    }

最后，稍微改改，就能改成反转 m 到 n 之间的节点。

3、代码

遍历：

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if(head == null){
            return head;
        }

        // 使用一个 dummy 节点就不用管从头开始还是从中间开始
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode p = dummy, q = dummy;

        for(int i = 1; i < left; i++){
            p = p.next;
        }

        // 要改变节点的前一个节点
        // 因为使用头插法反转
        ListNode start = p;
        p = p.next;
        ListNode end = p;
        start.next = null;
        for(int i = left; i <= right; i++){
            q = p.next;
            ListNode nextNode = start.next;
            p.next = nextNode;
            start.next = p;
            p = q;
        }
        end.next = p;

        return dummy.next;
    }
}

递归：

public class ReverseList {

    ListNode end = null;

    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(m == 1){
            return reverseListNodeN(head, n);
        }
        head.next = reverseBetween(head.next, m - 1, n - 1);

        return head;
    }

    public ListNode reverseListNodeN(ListNode head, int m){
        if(m == 1){
            end = head.next;
            return head;
        }

        ListNode last = reverseListNodeN(head.next, m - 1);
        head.next.next = head;
        head.next = end;
        return last;
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(3);
        ListNode l4 = new ListNode(4);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;

        ListNode root = new ReverseList().reverseBetween(l1, 1, 4);
        while (root != null){
            System.out.println(root.val);
            root = root.next;
        }
    }
}