递归的反转链表

作者：老刘
链接：https://www.zhihu.com/question/339135205/answer/794671353

每K个节点为一组反转链表，并从头部开始

例子：

链表:1->2->3->4->5->6->7->8->null, K = 3。
输出：1->2->5->4->3->8->7->6->null

解析：假设方法reverseKNode()的功能是将单链表的每K个节点之间逆序(从头部开始组起;reverse()方法的功能是将一个单链表逆序。
把前面K个节点与后面的节点分割出来

temp指向的剩余的链表，可以说是原问题的一个子问题。我们可以调用reverseKNode()方法将temp指向的链表每K个节点之间进行逆序。再调用reverse()方法把head指向的那3个节点进行逆序，结果如下：

最后将两部分合起来

代码:

//k个为一组逆序
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode temp = head;
        for (int i = 1; i < k && temp != null; i++) {
            temp = temp.next;
        }
        //判断节点的数量是否能够凑成一组
        if(temp == null)
            return head;

        ListNode t2 = temp.next;
        temp.next = null;
        //把当前的组进行逆序
        ListNode newHead = reverseList(head);
        //把之后的节点进行分组逆序
        ListNode newTemp = reverseKGroup(t2, k);
        // 把两部分连接起来
        head.next = newTemp;

        return newHead;
    }

    //逆序单链表
    private static ListNode reverseList(ListNode head) {
        if(head == null || head.next == null)//递归出口
            return head;
        ListNode result = reverseList(head.next);//递归前应该做的操作为null，所以直接递归
        head.next.next = head;//处理第一个与递归结果的关系
        head.next = null;
        return result;
    }

每K个节点为一组反转链表，并从尾部开始

• 先进行逆序
• 再执行从头部开始的K个一组逆序
• 再逆序返回

  public ListNode solve(ListNode head, int k) {
    // 调用逆序函数
    head = reverse(head);
    // 调用每 k 个为一组的逆序函数（从头部开始组起）
    head = reverseKGroup(head, k);
    // 在逆序一次
    head = reverse(head);
    return head;
  }