Split Linked List in Parts

medium linked list

Problem

Given the head of a singly linked list and an integer k, split the list into k consecutive parts. The length of each part should be as equal as possible: no two parts should have a size differing by more than one. Parts may be null, and earlier parts should be no smaller than later parts.

Inputhead = [1,2,3,4,5,6,7,8,9,10], k = 3

Output[[1,2,3,4], [5,6,7], [8,9,10]]

10 nodes / 3 parts = 3 each with 1 extra → first part gets 4.

list (comma-separated)

def split_list_to_parts(head, k):
    n, cur = 0, head
    while cur: n += 1; cur = cur.next
    base, extra = divmod(n, k)
    ans = [None] * k
    cur = head
    for i in range(k):
        ans[i] = cur
        size = base + (1 if i < extra else 0)
        for _ in range(size - 1):
            if cur: cur = cur.next
        if cur:
            nxt = cur.next
            cur.next = None
            cur = nxt
    return ans

function splitListToParts(head, k) {
  let n = 0, cur = head;
  while (cur) { n++; cur = cur.next; }
  const base = Math.floor(n / k), extra = n % k;
  const ans = new Array(k).fill(null);
  cur = head;
  for (let i = 0; i < k; i++) {
    ans[i] = cur;
    const size = base + (i < extra ? 1 : 0);
    for (let j = 0; j < size - 1; j++) if (cur) cur = cur.next;
    if (cur) { const nxt = cur.next; cur.next = null; cur = nxt; }
  }
  return ans;
}

class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        int n = 0; ListNode cur = head;
        while (cur != null) { n++; cur = cur.next; }
        int base = n / k, extra = n % k;
        ListNode[] ans = new ListNode[k];
        cur = head;
        for (int i = 0; i < k; i++) {
            ans[i] = cur;
            int size = base + (i < extra ? 1 : 0);
            for (int j = 0; j < size - 1 && cur != null; j++) cur = cur.next;
            if (cur != null) { ListNode nxt = cur.next; cur.next = null; cur = nxt; }
        }
        return ans;
    }
}

vector<ListNode*> splitListToParts(ListNode* head, int k) {
    int n = 0; ListNode* cur = head;
    while (cur) { n++; cur = cur->next; }
    int base = n / k, extra = n % k;
    vector<ListNode*> ans(k, nullptr);
    cur = head;
    for (int i = 0; i < k; i++) {
        ans[i] = cur;
        int size = base + (i < extra ? 1 : 0);
        for (int j = 0; j < size - 1 && cur; j++) cur = cur->next;
        if (cur) { ListNode* nxt = cur->next; cur->next = nullptr; cur = nxt; }
    }
    return ans;
}

Explanation

We need to chop the list into k pieces that are as even as possible, where earlier pieces may be one node longer than later ones. The key is figuring out each part's size up front with simple division.

First we count the length n. Then base = n // k is the size everyone gets, and extra = n % k is how many leftover nodes there are. Those leftovers are handed out one each to the first extra parts, so part i has size base + 1 when i < extra, otherwise just base.

We then walk through the list once. For each part we record its starting node in ans[i], advance size - 1 steps to reach its last node, then cut the link by setting cur.next = None and moving cur on to start the next part.

When n < k, base is 0 and only the first few parts get a node; the rest stay None, which is exactly what the problem allows.

Example: [1..10] with k=3 gives base=3, extra=1. So sizes are 4, 3, 3, producing [1,2,3,4], [5,6,7], [8,9,10].

Time: O(n) Space: O(k)