K个一组反转链表

示例:

给定这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

解析1:K个一组的压栈
代码:

public ListNode reverseKGroup(ListNode head, int k) {
        Deque<ListNode> stack = new ArrayDeque<ListNode>();//节点栈
        ListNode dummy = new ListNode(0);//哑节点
        ListNode p = dummy;
        while (true) {//只要不break就执行，即遇到结束或者是剩单个节点
            int count = 0;
            ListNode tmp = head;
            while (tmp != null && count < k) {//k若是2
                stack.add(tmp);
                tmp = tmp.next;//1 2 3 4 5到3
                count++;
            }
            if (count != k) {
                p.next = head;
                break;
            }
            while (!stack.isEmpty()){
                p.next = stack.pollLast();//0指向2
                p = p.next;//p变到2
            }
            p.next = tmp;
            head = tmp;
        }
        return dummy.next;
    }

解析2:递归。开始拿出k个并反转，设置递归出口，进行递归(功能，完成第一组后面的k个一组反转)，再进行拼接

作者：老刘
链接：https://www.zhihu.com/question/339135205/answer/794671353
//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);
        head.next.next = head;
        head.next = null;
        return result;
    }