Hack University
482/670

482. Split Linked List in Parts

Medium

You are given head, the first node of a singly linked list (each ListNode has a val and a next pointer), and an integer k.

Chop the list into exactly k consecutive parts, as fairly as possible:

  • Every part is a contiguous run of the original nodes, in the original order — part 1 is the front of the list, part 2 continues where part 1 stopped, and so on.
  • No two part lengths may differ by more than one, and earlier parts are never shorter than later parts. Together those two rules force the sizes: with n nodes, the first n mod k parts have ⌊n / k⌋ + 1 nodes and the rest have ⌊n / k⌋.
  • If k exceeds the number of nodes, the trailing parts are empty (null).

Return a list of the k part heads, in order. Each part must be severed — the last node of every part has to end in null, not point on into the next part.

Example 1 — three nodes chopped into five partsn = 3, k = 5: base size ⌊3/5⌋ = 0, remainder 3, so parts 1–3 receive one node each and parts 4–5 are empty. Every non-empty part is severed — its node's next pointer becomes null instead of continuing down the original chain.
original list (n = 3)123cutcutk = 5 parts, sizes 1 · 1 · 1 · 0 · 0[1][2][3][][]part 1part 2part 3part 4part 5

Example 1:

Input: head = [1 → 2 → 3], k = 5

Output: [[1], [2], [3], [], []]

Explanation: Three nodes shared among five parts: base size ⌊3/5⌋ = 0 with remainder 3, so the first three parts get one node each and the last two are empty.

Example 2:

Input: head = [1 → 2 → … → 10], k = 3

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

Explanation: Ten nodes into three parts: base size ⌊10/3⌋ = 3 with remainder 1, so only the first part is one node longer — sizes 4, 3, 3.

Constraints:

  • 1 ≤ number of nodes ≤ 1000
  • 0 ≤ Node.val ≤ 1000
  • 1 ≤ k ≤ 50

Hints:

You can't divide fairly without knowing how much there is to divide — one full walk to count the nodes comes first.

With n nodes, every part gets at least ⌊n / k⌋ nodes, and the leftover n mod k nodes go one apiece to the earliest parts. Compute each part's size before touching any pointers.

Walk the list once more: for part i, record the current node as its head, advance size − 1 steps to the part's tail, save tail.next, then set tail.next = null. Forgetting that cut is the classic bug — every part would drag the whole rest of the list behind it.

▶ Run checks these sample cases. Submit also runs hidden edge cases.

Input: head = [1 → 2 → 3], k = 5

Expected output: [[1], [2], [3], [], []]