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

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

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
	  
	  	// 算法时间复杂度O(N)，额外空间复杂度O(1)
	  
        // 1.先定义两个指针start和end，分别指向前方的m位置和后方的n位置
        ListNode start = null;
        ListNode end = null;

        // 2.记录start指针的上一个结点allPre，end指针的下一个结点allPost
        ListNode allPre = head;     // 先把allPre指向head这个整个链表的起点，随着查找m可以往后移动head
        ListNode allPost = null;
        // 准备找到m和n位置对应的start和end，以及对应的allPre和allPost
        ListNode cur = head;
        for (int i = 1; cur != null; cur = cur.next, i++) {
            if (i == m) {
                start = cur;
            }
            if (i == n) {
                end = cur;
                allPost = end.next;
                break;
            }
            // 只有在i>1（让allPre落后一位）且i<m（还没找到start）时更新allPre
            if (i > 1 && i < m) {
                allPre = allPre.next;
            }
        }
        System.out.println("allPre: " + (allPre != null ? allPre.val : "null"));
        System.out.println("start: " + (start != null ? start.val : "null"));
        System.out.println("end: " + (end != null ? end.val : "null"));
        System.out.println("allPost: " + (allPost != null ? allPost.val : "null"));

        // 3.执行类似于上一题的方法，反转start和end之间的链表，返回反转后的起点newStart和终点newEnd
        ListNode newStart = end;
        ListNode newEnd = start;
        // 只有strat和end不指向同一个结点（反转区间>1）时，才有反转的必要
        if (start != end) {
            ListNode newPre = start;
            ListNode newCur = start.next;
            ListNode newNext = newCur.next;
            // 此处不用管newPre的next指向何方，因为这个newPre就是newEnd，是数组反转后的结尾，下文会令其指向allPost
            while(newCur != allPost) {
                newNext = newCur.next;
                newCur.next = newPre;
                System.out.println("结点" + newCur.val + "的反转已完成");
                newPre = newCur;
                newCur = newNext;
            }
        }

        // 4.令allPre指向newStart，令allPost指向newEnd
        // 注意allPre的边界判断！allPre可能与newEnd（start）重合！
        if (allPre == newEnd) {
            // 如果allPre 跟 newEnd（start） 是同一个结点（m=1的情况），说明start前面没有任何元素，这时可以直接移动head到链表区间反转后的起点，令head = newStart
            allPre = newStart;
            head = allPre;
        } else {
            // 否则，是正常情况，令allPre指向newStart，从newStart到newEnd是反转区间
            allPre.next = newStart;
        }
        newEnd.next = allPost;
        System.out.println("newEnd结点" + newEnd.val + "的下一个结点allPost是" + (allPost != null ? allPost.val : "null"));
        System.out.println("allPre结点" + allPre.val + "的下一个结点newStart是" + (newStart != null ? newStart.val : "null"));
        System.out.println("head结点" + head.val);
        return head;
    }
}