反转链表||（Leetcode第92题）

反转链表||（Leetcode第92题）

• 前言：

在上一篇文章中有写到Leetcode206题反转链表，写到两种方法，原地移动法和递归法，实则还有头插法，这里不再赘述。今天又刷到Leetcode第92题，比206题多写了一个条件，界定了反转范围，这里在上一篇的原地移动法的基础上作出解答：

• 完整题目如下：

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

示例 1：
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

• 解法思路：

根据left和right找到要反转的链表范围，反转该部分链表，再将反转后的链表连接回原链表

• 注意：

（1）链表若为空或者只有一个头节点，则直接返回头节点即可

（2）链表至少有两个节点的情况，用pre表示left的前一个元素，即开始反转的前一个节点，将right-left范围内的链表反转，然后将反转后的链表连在pre节点后面，注意反转界限的前后相连

（3）建立虚拟头节点，无需考虑从head节点即开始反转的情况，使用虚拟头节点，最后返回虚拟头节点.next即可

（4）left与right之间的节点反转后链表各变量的状态如下图，圈1和圈2两条线为应该链接的两条线（pre、cur、next为下面我的代码中自己定义的变量）：

•  代码：

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
                if (head == null || head.next == null) {
            return head;
        }
//        至少有两个节点
        ListNode dummyHead = new ListNode(501);
        dummyHead.next = head;
        ListNode pre = dummyHead;
//        开始反转链表的前一个节点
            for (int i = 0; i < left - 1; i++) {
                pre = pre.next;
            }
//        cur为开始反转的第一个节点
            ListNode cur = pre.next;
            ListNode next = cur.next;
            for (int i = 0; i < right - left; i++) {
                ListNode a = next.next;
                next.next = cur;
                cur = next;
                next = a;
            }
// 注意这里的关系
            pre.next.next=next;
            pre.next=cur;
        return dummyHead.next;

    }
}