反转链表的指定区域

/*

• @lc app=leetcode.cn id=92 lang=java
• [92] 反转链表 II
• https://leetcode-cn.com/problems/reverse-linked-list-ii/description/
• algorithms
• Medium (49.93%)
• Likes: 363
• Dislikes: 0
• Total Accepted: 49.4K
• Total Submissions: 98.8K
• Testcase Example: '[1,2,3,4,5]\n2\n4'
• 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
• 说明:
• 1 ≤ m ≤ n ≤ 链表长度。
• 示例:
• 输入: 1->2->3->4->5->NULL, m = 2, n = 4
• 输出: 1->4->3->2->5->NULL

*/

解题思路

凡是涉及反转的思路，都需要先打断链表重新组合，
如果反转指定区域，可以将中间需要选装的部分 截取出来 ，和剩余部分总共组成三段内容
比如链表：1->2->3->4->5->NULL，m = 3, n = 4可以拆分为：
左边：1->2
中间：3->4
右边：5->NULL

解题步骤

1. 其中 左边一段 需要记录最后一个节点 p1，用于后续再将整个链表衔接起来
2. 右边一段需要记录首节点 p2，同样用作后面衔接。
3. 然后准备旋转中间链表

• 开始节点为p1.next。
• 旋转前需要记录首节点p3（最后衔接要用到）
• 旋转终止条件为：当前旋转节点不等于p2

4. 旋转后将p3节点指向p2 节点
5. 最后将p1节点指向旋转后的链表
6. 返回head节点，（所有的指针指向更改都是在操作head内部）

完。

注：有些case比较变态，会有m =1 的情况，此时要考虑无左边链表的情况，此时p1就应该等于head。
其余的：如果只有一个节点，再怎么玩都是一个，直接return head；
如果m = n，那么等于不需要旋转 ，也return head；

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head.next == null) { //只有一个节点
            return head;
        }
        if (m == n) { //不需要旋转
            return head;
        }
        ListNode startNode = null; //p1
        ListNode endNode = null; //p2
        ListNode cur = head;
        int count = 0;
        while (cur != null) { //找出需要拆分的位置p1，p2
            count++;
            if (count == m - 1) {
                startNode = cur;
            }
            if (count == n + 1) {
                endNode = cur;
            }
            cur = cur.next;
        }
        ListNode fromNode = startNode==null?head: startNode.next;
        //旋转中间链表
        cur = fromNode;
        ListNode newHead = null;
        while (cur != endNode) {
            ListNode temp = cur.next;
            cur.next = newHead;
            newHead = cur;
            cur = temp;
        }

        fromNode.next = endNode; //拼接尾部
        if (startNode == null) {
            head = newHead;
        }else
        {
            startNode.next = newHead; //拼接头部
        }
        return head;
    }
}