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

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) {
        if (head == null || head.next == null) {
            return head;
        }
        //遍历链表，重新添加成一个新的链表
        ListNode cycleNode = head;
        ListNode curNode = null;
        int size = size(cycleNode);

        //前部的最后一个节点
        ListNode frontNode = null;

        //尾部的第一个节点
        ListNode afterNode = null;

        //只添加尾部的头节点，用flag判断
        boolean afterFlag = true;

        for (int i = 0; i < size; i++) {
            //跳过前面m个，不要后面n个。
            if ((i + 1) < m) {
                //尾节点设置为空
                frontNode = addLast(frontNode, cycleNode.val);
            }
            if ((i + 1) >= m && (i + 1) <= n) {
                curNode = addFirst(curNode, cycleNode.val);
            }
            if (i + 1 > n && afterFlag) {
                afterNode = cycleNode;
                afterFlag = false;
            }
            cycleNode = cycleNode.next;
        }

        ListNode resultNode = null;

        if (frontNode != null) {
            resultNode = frontNode;
            while (curNode != null) {
                addLast(resultNode, curNode.val);
                curNode = curNode.next;
            }
        } else {
            resultNode = curNode;
        }

        while (afterNode != null) {
            addLast(resultNode, afterNode.val);
            afterNode = afterNode.next;
        }

        return resultNode;
    }

    /**
     * 在链表尾，增加单个末位节点
     *
     * @param head
     * @param data
     */
    protected ListNode addLast(ListNode head, int data) {
        ListNode addNode = new ListNode(data);
        if (head == null) {
            //这里其实也传不出去，只是没用上。
            head = addNode;
            return head;
        }

        ListNode curNode = head;
        while (curNode.next != null) {
            curNode = curNode.next;
        }

        curNode.next = addNode;
        return head;
    }

    /**
     * 在链表头，增加单个首位节点
     *
     * @param head
     * @param data 要增加的首位节点的值
     * @return
     */
    protected ListNode addFirst(ListNode head, int data) {
        ListNode curNode = new ListNode(data);
        curNode.next = head;
        head = curNode;
        return head;
    }

     /**
     * 得到单链表的长度
     *
     * @param head
     * @return
     */
    protected int size(ListNode head) {
        ListNode node = head;
        int index = 0;
        if (node == null) {
            return index;
        }
        while (node != null) {
            index++;
            node = node.next;
        }
        return index;
    }
}