LeetCode-92题： 反转链表 II（原创）

【题目描述】

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
【题目链接】. - 力扣（LeetCode）

【解题代码】

package list;

import list.base.ListNode;

public class ReverseBetween {
    public static void main(String[] args) {
        //int[] dataArray = new int[]{1, 2, 3, 4, 5};
        int[] dataArray = new int[]{1, 2, 3};
        ListNode head1 = ListNode.makeList(dataArray);
        ListNode head2 = new ReverseBetween().reverseBetween(head1, 1, 2);
        head2.printList();

    }

    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 特殊情况处理
        if (head.next == null || left == right) return head;

        // 定义一个左节点变量
        ListNode leftNode = head;
        // 定义一个左节点的前一节点
        ListNode leftPre = (left == 1) ? null : head;
        int i = 0;
        // 从节点首位置行走left步，找到左节点
        for (; i < left - 1; i++) {
            if (leftNode == null) return null;
            leftPre = leftNode;
            leftNode = leftNode.next;
        }
        // 定义一个右节点
        ListNode rightNode = leftNode;
        // 从节点当前位置继续行走一共right步，找到右节点
        for (; i < right - 1; i++) {
            if (rightNode == null) return null;
            rightNode = rightNode.next;
        }
        // 定义一个右节点的后一节点
        ListNode rightNext = rightNode.next;
        ListNode curNode = leftNode, lastNode = rightNext, nextNode;
        // 对从左位置节点开始到右节点后一节点，进行翻转
        while (curNode != rightNext) {
            nextNode = curNode.next;
            curNode.next = lastNode;
            lastNode = curNode;
            curNode = nextNode;
        }

        // 如果node1和下一个节点都不为空，将左节点的前节点的下一个节点指向右位置节点
        if (leftPre != null && leftPre.next != null )
            leftPre.next = rightNode;
        else // 否则链表首节点就是右位置节点
            head = rightNode;

        // 返回结果
        return head;
    }
}

【解题思路】

        拿到题目，思考一下就发现这道题就是链表翻转的通用版本. - 力扣（LeetCode），即常见的链表翻转是将长度为n的链表从位置1到位置n的节点进行翻转。把这个算法改写成为通用的链表翻转算法即可，即链表中间一段按通用的翻转算法将左位置到右位置下一节点（左开右闭）这一段节点进行翻转，最后将左位置前一节点指向翻转后的一段链表表的首节点（即右位置）即可，按照这个思路很快就写出算法代码，并提交成功，解题步骤如下：

【解题步骤】

1. 定义一个左节点和左节点的前一节点变量,考虑一下特殊情况

   ListNode leftNode = head;
   ListNode leftPre = (left == 1) ? null : head;

2. 从节点首位置行走left步，找到左节点，左节点前节点亦步亦趋

   int i = 0;
   // 从节点首位置行走left步，找到左节点
   for (; i < left - 1; i++) {
       if (leftNode == null) return null;
       leftPre = leftNode;
       leftNode = leftNode.next;
   }

3. 定义一个右节点从节点当前位置继续行走一共right步，找到右节点

   // 定义一个右节点
   ListNode rightNode = leftNode;
   // 从节点当前位置继续行走一共right步，找到右节点
   for (; i < right - 1; i++) {
       if (rightNode == null) return null;
       rightNode = rightNode.next;
   }

4. 定义一个右节点的后一节点，并对从左位置节点开始到右节点后一节点，进行翻转

   // 定义一个右节点的后一节点
   ListNode rightNext = rightNode.next;
   ListNode curNode = leftNode, lastNode = rightNext, nextNode;
   // 对从左位置节点开始到右节点后一节点，进行翻转
   while (curNode != rightNext) {
       nextNode = curNode.next;
       curNode.next = lastNode;
       lastNode = curNode;
       curNode = nextNode;
   }

5. 处理一下，左节点的前节点将左节点翻转之后的节点挂接过来，并处理一下特殊情况

   if (leftPre != null && leftPre.next != null )
       leftPre.next = rightNode;
   else // 否则链表首节点就是右位置节点
       head = rightNode;

6. 最后返回结果

    return head;

【思考总结】

1. 一些经典算法都是一些特殊情况下的算法，可以考虑将其改装成通用的算法；
2. 对于链表算法，遍历是一定要搞清楚一些关键节点变量初始化和赋值，包括lastNode，curNode,nextNode等；
3. 链表算法设计时对于比如链表头，链表结尾等特殊情况一定要考虑的比较周到；
4. LeetCode解题之前，一定不要看题解，看了就“破功”了！