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

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 static ListNode reverseBetween(ListNode head, int m, int n) {
        //m=n,直接返回
        if (m == n) {
            return head;
        }
        //统计节点数量
        int count = 0;
        ListNode node = head;
        while (node != null) {
            count++;
            node = node.next;
        }
        //参照上一题，把链表分成三部分
        //第一部分,是不需要翻转的

        ListNode node1 = head;
        //第二部分,需要翻转的部分
        ListNode node2;
        //第三部分,是不需要翻转的
        ListNode node3 = null;
        //当前对象
        ListNode currentNode = head;
        //序号
        int i = 1;
        ListNode preNode1 = head;
        ListNode temp1 = head;
        ListNode temp2;
        node2 = head;

        while (currentNode != null) {
            if (i == m - 1) {
                preNode1 = currentNode;
                temp1 = currentNode.next;
                currentNode.next = null;
                currentNode = temp1;
                i++;
                continue;
            }
            if (i == m) {
                node2 = currentNode;
            }
            if (i == n) {
                temp2 = currentNode.next;
                currentNode.next = null;
                currentNode = temp2;
                i++;
                continue;
            }
            if (i == n + 1) {
                node3 = currentNode;
            }
            currentNode = currentNode.next;
            i++;
        }
        ListNode reverseNode = reverseList(node2);
        if (m == 1) {
            //m=1时只有两部分(缺少第一部分)，直接翻转第二部分连接第三部分就可以了
            if (node3 != null) {
                node2.next = node3;
            }
            return reverseNode;
        } else if (n == count) {
            //n==链表长度，此时也只有两部分(缺少第三部分),直接第一部分连接第二部分即可
            preNode1.next = reverseNode;
            return node1;
        } else {
            //这里有三部分
            preNode1.next = reverseNode;
            temp1.next = node3;
            return node1;
        }
    }

    public static ListNode reverseList(ListNode head) {
        if (head != null && head.next != null && head.next.next != null) {
            ListNode preNode = head;
            ListNode current = head.next;
            ListNode nextNode;
            //最开始的头节点指向空
            preNode.next = null;
            while (current != null) {
                //先获取下一个节点
                nextNode = current.next;
                //当前节点指向上一个节点
                current.next = preNode;
                //上一个节点赋值为当前节点
                preNode = current;
                //当前节点往后走一步
                current = nextNode;
            }
            return preNode;
        } else if (head != null && head.next != null && head.next.next == null) {
            ListNode nextNode = head.next;
            head.next = null;
            nextNode.next = head;
            return nextNode;
        } else {
            return head;
        }
    }
}