本文为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
这个题目麻烦的地方在于边界情况太多。但简单而言,可按照如下处理:
/** * 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能够再完善下测试数据集。