必会算法：反转链表Ⅱ

阅读本文前，请务必先阅读必会算法：反转链表Ⅰ

##题目

上一篇文章咱们解决了如何反转整个链表的问题

那么如何反转一个链表的一部分节点呢？

图片

##解题思路

比如我们要反转下边这个链表的3~7范围的节点

图片

我们可以把这个链表分成三个部分了

其中1~2和8是不需要做任何操作的

图片

只有3~7部分的链表需要被反转，而整个链表的反转我们已经知道怎么做了

图片

反转3~7部分的链表之后，只需要让2->7、3->8就能解决这个题目了

图片

在这个过程中，只需要记录几个关键的节点就行了

即：

第一部分链表的起始节点（1节点）

第一部分链表的结尾节点（2节点）

第二部分链表的起始节点（3节点）

第二部分链表的结尾节点（7节点）

第三部分链表的起始节点（8节点）

图片

##算法图解

考虑到指定的反转范围可能是从第一个节点开始的

我们需要先定义一个“-1”节点

令“-1”节点的next指向链表的起始节点

然后按照解题思路就能顺利解题了

结合“必会算法：反转链表Ⅰ”中定义的节点，我们可以定义以下几个节点来标记关键节点

第一部分链表的起始节点：”-1“节点的next节点

第一部分链表的结尾节点：pointerEnd指向的节点

第二部分链表的起始节点：head指向的节点

第二部分链表的结尾节点：pre指向的节点

第三部分链表的起始节点：next指向的节点

初始位置如下图

图片

根据给定需要反转的起始位置

通过遍历链表，可将pointerEnd节点指向2

pre和head节点指向3，即需要反转链表的起始位置

图片

然后定义cur和next节点

图片

接下来的操作就是反转第二部分整个链表

图片 图片

直到pre指向要求反转链表的截止位置，第七个节点

图片

此时已完成节点的反转，并且关键节点都有标记

令

pointerEnd.next = pre

head.next = cur

返回”-1“节点的next就可以了

图片

##代码实现

    public static Node reverseRangeLinkedList(Node head, int start, int end) {

        if (head == null || head.next == null) {
            return head;
        }
        Node pointer = new Node(-1, head);
        Node pre = pointer;
        Node pointerEnd = pre;
        for (int i = 0; i < start; i++) {
            pointerEnd = pre;
            pre = pre.next;
        }
        head = pre;
        Node cur = pre.next;
        Node next = cur;
        pre.next = null;

        while (next != null && start < end) {
            next = next.next;
            cur.next = pre;
            pre = cur;
            cur = next;
            start++;
        }

        pointerEnd.next = pre;
        head.next = cur;

        return pointer.next;
    }

算法时间复杂度O(end)，end为要求反转范围的截止位置

算法空间复杂度O(1)

测试一下

    public static void main(String[] args) {
        Node head = new Node(1);
        Node temp = head;
        for (int i = 2; i < 10; i++) {
            temp.next = new Node(i);
            temp = temp.next;
        }
        int start = 3;
        int end = 8;
        System.out.println(head + "::反转::" + reverseRangeLinkedList(head, start, end));
    }

图片

文/戴先生@2021年11月20日

---end---