每天一道算法题

LeetCode第25题：翻转链表 K个数为一组

这道题初看有点难，其实可以拆解。我们将链表按K拆解为多个子链表，子链表各自翻转之后拼接到一起即可，具体的可以看代码注释。

/**
     * 这里思路是遍历链表，截取指定长度的链表整个翻转，同时记录首尾节点，之后拼接起来就行
     */
    public static ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null || k < 2) {
            return head;
        }
        int i = k - 1;
        // 虚拟空节点，最终返回使用
        ListNode ans = new ListNode(0);
        // 这个节点用来记录翻转后的尾节点用于与下个翻转后的节点拼接
        ListNode node = ans;
        // 当前的头节点，翻转后就是当前序列的尾节点
        ListNode last = head;
        // 记录一下当前翻转后需要处理的下一个节点
        ListNode next;
        while (head != null) {
            head = head.next;
            if (head == null) {
                node.next = last;
                break;
            }
            if (--i == 0) {
                i = k - 1;
                next = head.next;
                head.next = null;
                node.next = reverse(last);
                node = last;
                head = next;
                last = head;
            }

        }

        return ans.next;
    }

    /**
     * 传进来的链表整个翻转
     */
    private static ListNode reverse(ListNode head) {
        ListNode link = new ListNode(0, head.next);
        ListNode cur = head.next;
        head.next = null;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = head;
            link.next = cur;

            cur = next;
            head = link.next;
        }
        return link.next;
    }