描述

将一个节点数为 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;
    }
}

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

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

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