Split Linked List in Parts — Even Distribution
Advertisement
Problem 234 · Split Linked List in Parts
Difficulty: Medium · Pattern: Even Distribution
Solutions
# Python
def splitListToParts(head, k):
# Count length
n = 0; cur = head
while cur: n += 1; cur = cur.next
part_size, extra = divmod(n, k)
res = []
cur = head
for i in range(k):
res.append(cur)
size = part_size + (1 if i < extra else 0)
for _ in range(size - 1):
if cur: cur = cur.next
if cur:
cur.next, cur = None, cur.next
return res
// Java
public ListNode[] splitListToParts(ListNode head, int k) {
int n = 0; ListNode cur = head;
while (cur != null) { n++; cur = cur.next; }
int size = n / k, extra = n % k;
ListNode[] res = new ListNode[k];
cur = head;
for (int i = 0; i < k; i++) {
res[i] = cur;
int len = size + (i < extra ? 1 : 0);
for (int j = 0; j < len-1; j++) if (cur != null) cur = cur.next;
if (cur != null) { ListNode nxt = cur.next; cur.next = null; cur = nxt; }
}
return res;
}
Complexity
- Time: O(n + k)
- Space: O(k) for output array
Advertisement