1. 问题描述

问题主要就是将链表从m,n翻转其中的节点，包含m和n这个节点
1<=m<=n<=head.length
1->2->3->4->5->NULL m=2,n=4 即反转m与n之间的链表
1->4->3->2->5->NULL

2. 思路

2.1 思路1

思路1的话主要是找到m，然后遍历找到n，然后翻转m-n之间的节点，然后将前后拼接起来即可

     public ListNode reverseBetweenII(ListNode head, int m, int n) {
        if (head == null || head.next == null) return head;
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        int cnt = 0;
        ListNode pre = dummyNode;// 设置虚拟节点
        ListNode cur = pre.next;// 设置头节点
        while (cur != null) {
            cnt += 1;
            if (cnt == m) {// 找到第一个节点
                ListNode t = cur;// 记录下来拼接尾节点的前一个节点
                while (cnt != n) {
                    cnt += 1;
                    cur = cur.next;
                }
                // temp作为尾节点
                ListNode temp = cur.next;
                cur.next = null;// 切断联系
                ListNode node1 = pre.next;// 记录需要翻转的部分
                pre.next = null;// 切断联系
                pre.next = reverseNode(node1);// 翻转，然后头节点拼接上
                t.next = temp;// 尾节点拼接，返回即可
                return dummyNode.next;
            }
            cur = cur.next;
            pre = pre.next;
        }
        return null;
    }

    private ListNode reverseNode(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return head;
        ListNode p = reverseNode(head.next);// 一直遍历找最后一个
        head.next.next = head;// 通过修改空间中的指针指向，这里实质修改了节点与p的关系
        head.next = null;// 切点head节点的联系
        return p;
    }

2.2 思路2

思路2的话主要是通过递归的方法来，如果是从m=1开始翻转，则直接返回翻转后的。这里的翻转是记录尾节点即tailNode，然后再中途修改head指针与node指针之间的关系，从而实现链表翻转。如果是画图的话，可以看到，所有的节点其实就是从节点的上一个节点插入到tailNode前面，从而维持相对的关系。

    ListNode tailNode = null;

    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (m == 1) {
            // 如果是第一个节点开始，全都翻转
            return reverseN(head, n);
        }
        // 因为翻转的是相对大小位置，所以m-1，则n-1，需要对应变化才奏效
        head.next = reverseBetween(head.next, m - 1, n - 1);
        return head;
    }


    private ListNode reverseN(ListNode head, int n) {
        // 获取到尾节点，就是为了待会连接的问题
        if (n == 1) {
            tailNode = head.next;// 保留尾部节点
            return head;
        }
        // 递归向后走
        ListNode node = reverseN(head.next, n - 1);
        // 改变节点与node的指向
        head.next.next = head;
        // 实质就是往靠近tailNode的位置插入
        head.next = tailNode;
        // 返回node
        return node;
    }

3. 小结

这道题之前也做过，但是许久不做又生疏了，但是如果做也可以做出来。只是链表的转向真的比较有趣。如果不熟悉最好打断点，然后画图，还是比较简单的。

Keep thinking, keep coding! 加油

2020-08-25写于深圳南山