题解 | #链表内指定区间反转#

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
        if (m == n)
            return head;
        if (head == null)
            return null;
        
        ListNode l = head, r, l_temp = l;
        ListNode h1 = head, h2, h3;
        
        // 计算长度
        int len = 1;
        while (l.next != null) {
            l = l.next;
            len++;
        }
        
        l = head;
        for (int i = 1; i < m; i ++) {
            l_temp = l; // 暂存
            l = l.next;
        }
        
        r = l;
        h2 = l;
        for (int i = 0; i < n - m; i ++) {
            r = r.next;
        }
        
        h3 = r.next;
        r.next = null;
        
        h2 = ReverseList(h2);
        
        if (m == 1) {
            return add(null, h2, h3);
        }
        l_temp.next = null;
        return add(h1, h2, h3);
    }
    
    public ListNode ReverseList(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        ListNode r = head.next;
        ListNode l = head;
        ListNode t = r.next;
        head.next = null;
         
        while(t != null) {
            r.next = l;
            l = r;
            r = t;
            t = r.next;
        }
        r.next = l;
        return r;
    }
    
    public ListNode add(ListNode h1, ListNode h2, ListNode h3) {
        if (h1 == null){
            h1 = h2;
            h2 = h3;
            h3 = null;
        }
        if (h1 == null){
            h1 = h2;
            h2 = h3;
            h3 = null;
        }

        ListNode tail = h1;
        while (tail.next != null) {
            tail = tail.next;
        }
        tail.next = h2;
        while (tail.next != null) {
            tail = tail.next;
        }
        tail.next = h3;
        return h1;
    }
}

主要就是分成三块链表然后用上一题翻转链表对中间反转， 先找到起始点然后切断链表，注意下特别情况m==1的时候不应该切断而应该让第一个链表为null 到不到尾应该没关系