leetcode刷题（39）——反转链表 II

这道题可以说是非常难的，2中解法，迭代和递归，递归更加难想出来

解法1:迭代链接反转 算法

在看具体算法之前，有必要先弄清楚链接反转的原理以及需要哪些指针。举例而言，有一个三个不同结点组成的链表 A → B → C，需要反转结点中的链接成为 A ← B ← C。

假设我们有两个指针，一个指向结点 A，一个指向结点 B。 分别记为 prev 和 cur。则可以用这两个指针简单地实现 A 和 B 之间的链接反转：

cur.next = prev

这样做唯一的问题是，没有办法继续下去，换而言之，这样做之后就无法再访问到结点 C。因此，我们需要引入第三个指针，用于帮助反转过程的进行。因此，我们不采用上面的反转方法，而是：

third = cur.next
cur.next = prev
prev = cur
cur = third

迭代 地进行上述过程，即可完成问题的要求。下面来看看算法的步骤。

如上所述，我们需要两个指针 prev 和 cur。 prev 指针初始化为 None，cur 指针初始化为链表的 head。 一步步地向前推进 cur 指针，prev 指针跟随其后。 如此推进两个指针，直到 cur 指针到达从链表头起的第 m 个结点。这就是我们反转链表的起始位置。 注意我们要引入两个额外指针，分别称为 tail 和 con。tail 指针指向从链表头起的第m个结点，此结点是反转后链表的尾部，故称为 tail。con 指针指向第 m 个结点的前一个结点，此结点是新链表的头部。下图可以帮助你更好的理解这两个指针。

在这里插入图片描述

tail 和 con 指针在算法开始时被初始化，在算法最后被调用，用于完成链表反转。 如前文所解释的那样，抵达第 m个结点后，在用到上述两个指针前，先迭代地反转链接。不断迭代，直到完成指向第 n 个结点的链接。此时，prev 指针会指向第 n 个结点。 我们使用 con 指针来连接 prev 指针，这是因为 prev 指针当前指向的结点(第 n 个结点)会代替第 m 个结点的位置。 类似地，我们利用 tail 指针来连接 prev 指针之后的结点（第 n+1 个结点）。 为了便于理清每个指针的用法，我们来看一个算法运行的实例。给定一个链表 7 → 9 → 2 → 10 → 1 → 8 → 6，我们需要反转从第 3 个结点到第 6 个结点的子链表。

在这里插入图片描述

从上图可以看到迭代法的前几步。第一步展示了两个指针的初始化，第三步展示了链表反转过程的初始位置。

在这里插入图片描述

上图详细显示了链接反转的过程以及反转两个结点的链接后如何向前移动。如下图所示，本步骤将执行多次。

在这里插入图片描述

如上图所示, 两个指针都已经到达最终位置。我们完成了子链表的反转工作。然而，还有一些链接需要调整。下图展示了利用 tail 和 con 指针完成链接调整的过程。

在这里插入图片描述

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {

        // Empty list
        if (head == null) {
            return null;
        }

        // Move the two pointers until they reach the proper starting point
        // in the list.
        ListNode cur = head, prev = null;
        while (m > 1) {
            prev = cur;
            cur = cur.next;
            m--;
            n--;
        }

        // The two pointers that will fix the final connections.
        ListNode con = prev, tail = cur;

        // Iteratively reverse the nodes until n becomes 0.
        ListNode third = null;
        while (n > 0) {
            third = cur.next;
            cur.next = prev;
            prev = cur;
            cur = third;
            n--;
        }

        // Adjust the final connections as explained in the algorithm
        if (con != null) {
            con.next = prev;
        } else {
            head = prev;
        }

        tail.next = cur;
        return head;
    }
}

复杂度分析 时间复杂度: O(N)。考虑包含 N 个结点的链表。对每个节点最多会处理 （第 n 个结点之后的结点不处理）。 空间复杂度: O(1)我们仅仅在原有链表的基础上调整了一些指针，只使用了 O(1) 的额外存储空间来获得结果。