描述

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。 例如： 给出的链表为 1→2→3→4→5→NULL, m=2,n=4m=2,n=4, 返回 1→4→3→2→5→NULL.

问题分析

练习了简单的链表反转，我们知道可以通过双指针的方式来完成链表的反转，那么我们应该如何把指定区间的链表反转和这个联系起来呢，我们可以找到prevMNode（mNode的前一个节点），mNode，nNode，nextNNode，然后将mNode，nNode这段链表反转，最后将这三段链表连接起来，组成一个新的链表，这样，指定区间的链表反转就完成了，下面我们使用图例来看一下链表的反转过程。

通过图例，我们可以看出链表反转的过程，同时，我们也发现了一个问题，当我们是从链表的头部开始反转的时候，这个时候，我们还需要判断mNode是否有prevMNode，这会让程序变得复杂，那么，我们有什么好的办法呢？答案就是定义一个虚拟的头结点。

算法实现

下面，我们来看一下代码实现

/* * public class ListNode { *   int val; *   ListNode next = null; * } */public class Solution {    /**     *      * @param head ListNode类      * @param m int整型      * @param n int整型      * @return ListNode类     */    public ListNode reverseBetween (ListNode head, int m, int n) {        // write code here        // 判断不需要反转的条件        if(head == null || m >= n) {            return head;        }        // 定义虚拟的头结点        ListNode dummy = new ListNode(-1);        dummy.next = head;        head = dummy;                ListNode prevM = head;        // 寻找prevM        for(int i = 0; i < m - 1; i++) {            prevM = prevM.next;        }        // prevM的下一个节点即为mNode        ListNode mNode = prevM.next;        ListNode nNode = mNode;        ListNode postNode = nNode.next;        // 使用双指针法反转链表        for(int i = m; i < n; i++) {            ListNode next = postNode.next;            postNode.next = nNode;            nNode = postNode;            postNode = next;        }        // 重组链表        mNode.next = postNode;        prevM.next = nNode;        // 虚拟头结点的下一个节点即为新的头结点        return dummy.next;    }}

算法需要练习才能掌握精髓，附上算法练习地址，有需要的小伙伴可以上去练习一下

链表内指定区间反转_牛客题霸_牛客网

注：牛客网上的算法题按照专题分类，更适合突击训练使用