LeetCode 25. Reverse Nodes in k-Group

本文为LeetCode 25. Reverse Nodes in k-Group 的题解。

题意

给定一个链表，k个一组反转链表。

k 是一个正数，且小于链表长度。如果按照k个一组，最后剩下的不组k，则不反转剩下的元素。

例子:

对于链表: 1->2->3->4->5

若 k = 2, 应返回: 2->1->4->3->5

若 k = 3, 应返回: 3->2->1->4->5

注意:

• 只允许O(1)的空间复杂度。
• 不可以改变节点的值。

题解

这个题目麻烦的地方在于边界情况太多。但简单而言，可按照如下处理：

1. k个一组分组，满k个为完整组，不满k个为不完整组
2. 对于完整组，反转，然后接到结果中
3. 对于不完整组，直接接到结果中

代码

/**
 * https://www.robberphex.com/reverse-nodes-in-k-group/
 * Runtime: 1 ms, faster than 41.14% of Java online submissions for Reverse Nodes in k-Group.
 * Memory Usage: 38.5 MB, less than 24.80% of Java online submissions for Reverse Nodes in k-Group.
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        int length = 0;

        // 存储返回结果的第一个和最后一个节点
        ListNode totalHead = null;
        ListNode totalTail = null;
        // 存储当前组中第一个和最后一个节点
        ListNode segHead = null;
        ListNode segTail = null;
        // 遍历
        while (head != null) {
            // 将当前元素放到组中队首
            // 即反转了顺序
            ListNode tmp = head.next;
            head.next = segHead;
            segHead = head;

            // group首
            if (length % k == 0) {
                segTail = head;
            }

            // group 尾
            if (length % k == k - 1) {
                // 如果结果的head没有出现，则设置
                if (totalHead == null) {
                    totalHead = segHead;
                }
                // 如果有队列尾，则将当前组添加到尾部
                if (totalTail != null) {
                    totalTail.next = segHead;
                }
                totalTail = segTail;
                // 开始新的组
                segHead = null;
            }

            head = tmp;
            length++;
        }

        // 如果还剩下不完整的组，我们需要再次反转
        // 将其转换为正序
        if (length % k != 0) {
            head = segHead;
            segHead = null;
            while (head != null) {
                ListNode tmp = head.next;
                head.next = segHead;
                segHead = head;
                head = tmp;
            }
        }
        // 将不完整组添加到结果中
        if (totalTail != null) {
            totalTail.next = segHead;
        } else {
            totalHead = segHead;
        }
        return totalHead;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        ListNode res = new Solution().reverseKGroup(head, 2);

        while (res != null) {
            System.out.print(res.val);
            System.out.print(", ");
            res = res.next;
        }
        System.out.println();
        // 输出 2, 1, 4, 3, 5,
    }
}

备注

看了下，还有更快的 0ms 的解法：

/**
 * https://www.robberphex.com/reverse-nodes-in-k-group/
 * Runtime: 0 ms, faster than 100.00% of Java online submissions for Reverse Nodes in k-Group.
 * Memory Usage: 38.5 MB, less than 24.52% of Java online submissions for Reverse Nodes in k-Group.
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode cur = head;
        int cnt = 0;
        ListNode prev = null;
        while (cnt < k) {
            if (cur == null) {
                // 当前不足k个，直接返回
                return head;
            }
            prev = cur;
            cur = cur.next;
            cnt++;
        }
        // 将k个从原链表中切出来
        prev.next = null;

        // 反转原链表，这时prev是头，head是尾了
        reverse(head);

        // 继续递归分剩下的
        head.next = reverseKGroup(cur, k);

        return prev;
    }

    private ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        ListNode res = new Solution().reverseKGroup(head, 2);

        while (res != null) {
            System.out.print(res.val);
            System.out.print(", ");
            res = res.next;
        }
        System.out.println();
        // 输出 2, 1, 4, 3, 5,
    }
}

但是这个解法根本不符合要求啊，reverse空间复杂度 O(n) ，reverseKGroup空间复杂度 O(n/k)+O(n)≈O(n) 。希望LeetCode能够再完善下测试数据集。