Problem
Given a (singly) linked list with head node root, write a function to 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 1. This may lead to some parts being null.
- The parts should be in order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal parts occurring later.
- Return a List of ListNode’s representing the linked list parts that are formed
Example:
[1,2,3,4,5,6,7,8,9,10], k=3
ans = [ [1,2,3,4] [5,6,7] [8,9,10] ]
- If there are
N
nodes in the linked listroot
, then there areN/k
items in each part, plus the firstN%k
parts have an extra item. We can countN
with a simple loop. - Now for each part, we have calculated how many nodes that part will have:
width + (i < remainder ? 1 : 0)
. We create a new list and write the part to that list.
Implementation
public ListNode[] splitListToParts(ListNode root, int k) {
ListNode cur = root;
int N = 0;
while (cur != null) {
cur = cur.next;
N++;
}
int width = N / k, rem = N % k;
ListNode[] ans = new ListNode[k];
cur = root;
for (int i = 0; i < k; ++i) {
ListNode head = new ListNode(0), write = head;
for (int j = 0; j < width + (i < rem ? 1 : 0); ++j) {
write = write.next = new ListNode(cur.val);
if (cur != null) cur = cur.next;
}
ans[i] = head.next;
}
return ans;
}