[数据结构与算法]NC21 链表内指定区间反转

NC21 链表内指定区间反转

描述
将一个链表\ m m 位置到\ n n 位置之间的区间反转，要求时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。
例如：
给出的链表为 1\to 2 \to 3 \to 4 \to 5 \to NULL1→2→3→4→5→NULL, m=2,n=4m=2,n=4,
返回 1\to 4\to 3\to 2\to 5\to NULL1→4→3→2→5→NULL.
注意：
给出的 mm,nn 满足以下条件：
1 \leq m \leq n \leq 链表长度1≤m≤n≤链表长度
示例1
输入：
{1,2,3,4,5},2,4
复制
返回值：
{1,4,3,2,5}

import java.util.*;

/*
 * 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
        ListNode dummy = new ListNode(0) ;
        dummy.next = head ;
        ListNode curt = dummy ;
        for(int i = 0 ; i < m -1 ; i++){
            curt = curt.next ;
            if(curt == null){
                return head ;
            }
        }
        ListNode nm = curt.next ;
        ListNode nn = dummy;
        for(int i = 0 ; i < n ; i++){
            nn = nn.next ;
            if(nn == null){
                return head ;
            }
        }
        ListNode nnplus = nn.next ;
        ListNode prev = curt ;
        ListNode tail = nm ;
        while(tail != nnplus){
            ListNode temp = tail.next ;
            tail.next = prev ;
            prev = tail ;
            tail = temp ;
        }
        nm.next = nnplus ;
        curt.next = nn ;
        return dummy.next;
    }
}