🤔25.Reverse Nodes in k-Group (H)

https://leetcode.com/problems/reverse-nodes-in-k-group/

1.Description(Hard)

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed. Only constant memory is allowed.

Example

Given this linked list:1->2->3->4->5

For k = 2, you should return:2->1->4->3->5

For k = 3, you should return:3->2->1->4->5

2.Code

Version 1: Non-Recursive

每K个元素，翻转一次。最后一次如果不到K，再翻转回来即可。

http://bangbingsyb.blogspot.ca/2014/11/leetcode-reverse-nodes-in-k-group.html

几乎用到linked list题所有的技巧。

1. p指针总是指向每次要反转的k个节点的前一个节点。因为反转后仍然要接回这个节点之后。

2. ln8：如果p指针后没有节点或只剩一个节点了，那么整个反转结束。

3. ln11-17：尝试反转k个节点，如果遇到尾部，则提前结束。i记录了反转多少次。注意，要反转k个节点的话，实际反转指针只需要k-1次。

4. ln19-24：如果成功反转k个节点，则i=k-1。此时将反转的k个节点两头接回，并将p移动到反转后k个节点的最后一个节点处，以备继续反转之后的k个节点。

5. ln25-35：如果没能反转k个节点就遇到尾部。则逆向还原。

/*就是区间的reverse。因为题目要求的是k group逆转嘛。注意人返回的是最后一个(last)节点，
     * 这样下一个k-group就可以用上了。牛人的想法真是周到体贴～～。
     * 主方法里面，遍历的过程中每次都计数，每次到达k个节点，就可以使用pre和head.next调用上面的方法逆转了.
    */
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head==null || k==1){
            return head;
        }

        ListNode dummy=new ListNode(0);
        dummy.next=head;
        ListNode pre=dummy;
        int i=0;
        while(head!=null){
            i++;
            if(i%k==0){
                pre=reverse(pre,head.next);
                head=pre.next; //the first element in next k element
            }
            else{
                head=head.next;
            }
        }
        return dummy.next;
    }

    /**
     * Reverse a link list between pre and next exclusively
     * an example:
     * a linked list:
     * 0->1->2->3->4->5->6
     * |           |   
     * pre        next
     * after call pre = reverse(pre, next)
     * 
     * 0->3->2->1->4->5->6
     *          |  |
     *          pre next
     * @param pre 
     * @param next
     * @return the reversed list's last node, which is the precedence of parameter next
     */
    //保持一个invariant就是last节点始终在最后（cur的前面一个）
    public ListNode reverse(ListNode pre,ListNode end){
        ListNode last=pre.next;
        ListNode current=last.next;
        while(current!=end){
            last.next=current.next;
            current.next=pre.next;
            pre.next=current;
            current=last.next;           
        }
        return last;
    }

Version 2: Recursive

https://labuladong.github.io/algo/2/17/18/ 首先，前文 学习数据结构的框架思维提到过，链表是一种兼具递归和迭代性质的数据结构，认真思考一下可以发现这个问题具有递归性质。

什么叫递归性质？直接上图理解，比如说我们对这个链表调用 reverseKGroup(head, 2)，即以 2 个节点为一组反转链表：

如果我设法把前 2 个节点反转，那么后面的那些节点怎么处理？后面的这些节点也是一条链表，而且规模（长度）比原来这条链表小，这就叫子问题。

我们可以直接递归调用 reverseKGroup(cur, 2)，因为子问题和原问题的结构完全相同，这就是所谓的递归性质。

发现了递归性质，就可以得到大致的算法流程：

1、先反转以 head 开头的 k 个元素。

2、将第 k + 1 个元素作为 head 递归调用 reverseKGroup 函数。

3、将上述两个过程的结果连接起来。

整体思路就是这样了，最后一点值得注意的是，递归函数都有个 base case，对于这个问题是什么呢？

题目说了，如果最后的元素不足 k 个，就保持不变。这就是 base case，待会会在代码里体现。

二、代码实现

首先，我们要实现一个 reverse 函数反转一个区间之内的元素。在此之前我们再简化一下，给定链表头结点，如何反转整个链表？

// 反转以 a 为头结点的链表
ListNode reverse(ListNode a) {
    ListNode pre, cur, nxt;
    pre = null; cur = a; nxt = a;
    while (cur != null) {
        nxt = cur.next;
        // 逐个结点反转
        cur.next = pre;
        // 更新指针位置
        pre = cur;
        cur = nxt;
    }
    // 返回反转后的头结点
    return pre;
}

这次使用迭代思路来实现的，借助动画理解应该很容易。

「反转以 a 为头结点的链表」其实就是「反转 a 到 null 之间的结点」，那么如果让你「反转 a 到 b 之间的结点」，你会不会？

只要更改函数签名，并把上面的代码中 null 改成 b 即可：

/** 反转区间 [a, b) 的元素，注意是左闭右开 */
ListNode reverse(ListNode a, ListNode b) {
    ListNode pre, cur, nxt;
    pre = null; cur = a; nxt = a;
    // while 终止的条件改一下就行了
    while (cur != b) {
        nxt = cur.next;
        cur.next = pre;
        pre = cur;
        cur = nxt;
    }
    // 返回反转后的头结点
    return pre;
}

现在我们迭代实现了反转部分链表的功能，接下来就按照之前的逻辑编写 reverseKGroup 函数即可：

ListNode reverseKGroup(ListNode head, int k) {
    if (head == null) return null;
    // 区间 [a, b) 包含 k 个待反转元素
    ListNode a, b;
    a = b = head;
    for (int i = 0; i < k; i++) {
        // 不足 k 个，不需要反转，base case
        if (b == null) return head;
        b = b.next;
    }
    // 反转前 k 个元素
    ListNode newHead = reverse(a, b);
    // 递归反转后续链表并连接起来
    a.next = reverseKGroup(b, k);
    return newHead;
}

解释一下 for 循环之后的几句代码，注意 reverse 函数是反转区间 [a, b)，所以情形是这样的：

递归部分就不展开了，整个函数递归完成之后就是这个结果，完全符合题意：

三、最后说两句

从阅读量上看，基本数据结构相关的算法文章看的人都不多，我想说这是要吃亏的。

大家喜欢看动态规划相关的问题，可能因为面试很常见，但就我个人理解，很多算法思想都是源于数据结构的。我们公众号的成名之作之一，「学习数据结构的框架思维」就提过，什么动规、回溯、分治算法，其实都是树的遍历，树这种结构它不就是个多叉链表吗？你能处理基本数据结构的问题，解决一般的算法问题应该也不会太费事。

那么如何分解问题、发现递归性质呢？这个只能多练习，也许后续可以专门写一篇文章来探讨一下，本文就到此为止吧，希望对大家有帮助！