Given the head of a singly linked list and an integer k, split the linked list into k consecutive linked list parts.
The length of each part should be as equal as possible: no two parts should have a size differing by more than one. This may lead to some parts being null.
The parts should be in the order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal to parts occurring later.
Return an array of the k parts.
Example 1:
Input: head = [1,2,3], k = 5 Output: [[1],[2],[3],[],[]] Explanation: The first element output[0] has output[0].val = 1, output[0].next = null. The last element output[4] is null, but its string representation as a ListNode is [].
Example 2:
Input: head = [1,2,3,4,5,6,7,8,9,10], k = 3 Output: [[1,2,3,4],[5,6,7],[8,9,10]] Explanation: The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.
Constraints:
- The number of nodes in the list is in the range
[0, 1000]. 0 <= Node.val <= 10001 <= k <= 50
分隔链表。
给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。
每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1，也就是说可能有些部分为 null。
这k个部分应该按照在链表中出现的顺序进行输出，并且排在前面的部分的长度应该大于或等于后面的长度。
返回一个符合上述规则的链表的列表。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/split-linked-list-in-parts
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题意不难理解，给一个 linked list，请你按照规则分割成若干个子 linked list，以 ListNode[] 的形式输出。分割的要求是需要把 input 分成 K 个组，任何两组 node 之间的个数差不能大于 1。
这道题是 linked list 的实现题。根据分割的要求，我们会发现，如果 input 里有 len 个 node，那么每组需要有 len / k 个 node。如果 len 不能被 k 整除，剩下的 remainder 需要被平均分配给前几组node，前几组的 node 个数会是 len / k + 1。知道这个信息之后，就按长度把 list 分割好即可。
时间O(n)
空间O(n) - output
Java实现
1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode() {} 7 * ListNode(int val) { this.val = val; } 8 * ListNode(int val, ListNode next) { this.val = val; this.next = next; } 9 * } 10 */ 11 class Solution { 12 public ListNode[] splitListToParts(ListNode root, int k) { 13 ListNode[] res = new ListNode[k]; 14 // corner case 15 if (root == null) { 16 return res; 17 } 18 int len = 0; 19 ListNode cur = root; 20 while (cur != null) { 21 len++; 22 cur = cur.next; 23 } 24 25 // a index for the res array 26 int index = 0; 27 cur = root; 28 int each = len / k; 29 int remainder = len % k; 30 // first few groups have one more element 31 ListNode curHead = cur; 32 ListNode nextHead; 33 // a counter traverse the linkedlist 34 int p = 0; 35 for (int i = 0; i < remainder; i++) { 36 while (p < each && cur != null) { 37 cur = cur.next; 38 p++; 39 } 40 if (cur != null) { 41 nextHead = cur.next; 42 cur.next = null; 43 p = 0; 44 res[index] = curHead; 45 index++; 46 curHead = nextHead; 47 cur = nextHead; 48 } 49 } 50 // the rest of the groups have one less element 51 for (int j = remainder; j < len; j++) { 52 while (p < each - 1 && cur != null) { 53 cur = cur.next; 54 p++; 55 } 56 if (cur != null) { 57 nextHead = cur.next; 58 cur.next = null; 59 p = 0; 60 res[index] = curHead; 61 index++; 62 curHead = nextHead; 63 cur = nextHead; 64 } 65 } 66 return res; 67 } 68 }
如上这个代码中间有重复的部分，二刷的时候我换了一种做法，时间空间复杂度相同，但是简洁许多。
1 class Solution { 2 public ListNode[] splitListToParts(ListNode head, int k) { 3 int len = 0; 4 ListNode temp = head; 5 while (temp != null) { 6 len++; 7 temp = temp.next; 8 } 9 int each = len / k; 10 int remainder = len % k; 11 12 ListNode[] parts = new ListNode[k]; 13 ListNode cur = head; 14 for (int i = 0; i < k && cur != null; i++) { 15 parts[i] = cur; 16 int partSize = each + (i < remainder ? 1 : 0); 17 for (int j = 1; j < partSize; j++) { 18 cur = cur.next; 19 } 20 ListNode next = cur.next; 21 cur.next = null; 22 cur = next; 23 } 24 return parts; 25 } 26 }