92.Reverse Linked List II (M)

1.Description(Medium)

Reverse a linked list from position m to n.

Notice

Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.

Example

Given1->2->3->4->5->NULL, m =2and n =4, return1->4->3->2->5->NULL.

2.Code

Version 1: Non-Recursive

由于m=1时会变动头节点，所以加入一个dummy头节点

1.先找到第m个点(走m-1步)

2.prevm ->m-1

currentm -> m

currentn -> m

postn ->m+1

prevm 和currentm 一直保持不动 ，为了最后的连接存在，中间只移动currentn和postn

3.中间reverse n-m步（for i=m;i<n;i++）

这中间移动currentn和postn时要注意写法，不然会造成memeory limit exceed

4.最后currentn -> n; postn ->n+1

5.最终connect m-1.next=n; m.next=n+1

  public ListNode reverseBetween(ListNode head, int m , int n) {
       if(m>=n || head==null){
            return head;
        }

        ListNode dummy=new ListNode(0);
        dummy.next=head;
        ListNode temp=dummy;

        //m-1 steps reach to m-1 node
        for(int i=1;i<=m-1;i++){
            if(temp==null){
                return null;
            }
            temp=temp.next;
        }

        //define the m-1,m,n,n+1 node
        ListNode premNode=temp;  //keep use for connect
        ListNode mNode=temp.next;//keep use for connect
        ListNode nNode=mNode;
        ListNode postnNode=mNode.next;
        //need n-m-1 steps
        for(int i=m;i<n;i++){
            if(postnNode==null){
                return null;
            }

            ListNode post=postnNode.next;
            postnNode.next=nNode;
            //这里这样写就memory limit exceed
            //nNode=nNode.next;
            //postnNode=postnNode.next;
            nNode=postnNode;
            postnNode=post;          
        }

        //connect m-1->n;  m->n+1
        premNode.next=nNode;
        mNode.next=postnNode;

        return dummy.next;        
    }

Version 2: Recursive

反转链表前 N 个节点

这次我们实现一个这样的函数：

// 将链表的前 n 个节点反转（n <= 链表长度）
ListNode reverseN(ListNode head, int n)

比如说对于下图链表，执行 reverseN(head, 3)：

解决思路和反转整个链表差不多，只要稍加修改即可：

ListNode successor = null; // 后驱节点

// 反转以 head 为起点的 n 个节点，返回新的头结点
ListNode reverseN(ListNode head, int n) {
    if (n == 1) {
        // 记录第 n + 1 个节点
        successor = head.next;
        return head;
    }
    // 以 head.next 为起点，需要反转前 n - 1 个节点
    ListNode last = reverseN(head.next, n - 1);

    head.next.next = head;
    // 让反转之后的 head 节点和后面的节点连起来
    head.next = successor;
    return last;
}

具体的区别：

1、base case 变为 n == 1，反转一个元素，就是它本身，同时要记录后驱节点。

2、刚才我们直接把 head.next 设置为 null，因为整个链表反转后原来的 head 变成了整个链表的最后一个节点。但现在 head 节点在递归反转之后不一定是最后一个节点了，所以要记录后驱 successor（第 n + 1 个节点），反转之后将 head 连接上。

OK，如果这个函数你也能看懂，就离实现「反转一部分链表」不远了。

反转链表的一部分

现在解决我们最开始提出的问题，给一个索引区间 [m,n]（索引从 1 开始），仅仅反转区间中的链表元素。

ListNode reverseBetween(ListNode head, int m, int n)

首先，如果 m == 1，就相当于反转链表开头的 n 个元素嘛，也就是我们刚才实现的功能：

ListNode reverseBetween(ListNode head, int m, int n) {
    // base case
    if (m == 1) {
        // 相当于反转前 n 个元素
        return reverseN(head, n);
    }
    // ...
}

如果 m != 1 怎么办？如果我们把 head 的索引视为 1，那么我们是想从第 m 个元素开始反转对吧；如果把 head.next 的索引视为 1 呢？那么相对于 head.next，反转的区间应该是从第 m - 1 个元素开始的；那么对于 head.next.next 呢……

区别于迭代思想，这就是递归思想，所以我们可以完成代码：

ListNode reverseBetween(ListNode head, int m, int n) {
    // base case
    if (m == 1) {
        return reverseN(head, n);
    }
    // 前进到反转的起点触发 base case
    head.next = reverseBetween(head.next, m - 1, n - 1);
    return head;
}

至此，我们的最终大 BOSS 就被解决了。

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        // base case
        if (m == 1) {
            return reverseN(head, n);
        }
        // 前进到反转的起点触发 base case
        head.next = reverseBetween(head.next, m - 1, n - 1);
        return head;
    }

    ListNode successor = null; // 后驱节点
    // 反转以 head 为起点的 n 个节点，返回新的头结点
    ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            // 记录第 n + 1 个节点
            successor = head.next;
            return head;
        }
        // 以 head.next 为起点，需要反转前 n - 1 个节点
        ListNode last = reverseN(head.next, n - 1);

        head.next.next = head;
        // 让反转之后的 head 节点和后面的节点连起来
        head.next = successor;
        return last;
    }
}
// 详细解析参见：
// https://labuladong.github.io/article/?qno=92

最后总结

递归的思想相对迭代思想，稍微有点难以理解，处理的技巧是：不要跳进递归，而是利用明确的定义来实现算法逻辑。

处理看起来比较困难的问题，可以尝试化整为零，把一些简单的解法进行修改，解决困难的问题。

值得一提的是，递归操作链表并不高效。和迭代解法相比，虽然时间复杂度都是 O(N)，但是迭代解法的空间复杂度是 O(1)，而递归解法需要堆栈，空间复杂度是 O(N)。所以递归操作链表可以作为对递归算法的练习或者拿去和小伙伴装逼，但是考虑效率的话还是使用迭代算法更好。