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能够再完善下测试数据集。