VietMX Staff asked 1 year ago
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 list root, then there are N/k items in each part, plus the first N%k parts have an extra item. We can count N 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) {
}