Coding Interview PatternsSplit Linked List in Parts
MediumFast and Slow Pointers

Split Linked List in Parts

Explanation & Solution

Practice Problem

Description

Given the head of a singly linked list and an integer k, split the linked list into k consecutive parts as equally as possible.

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 to parts occurring later.

Return an array of k parts, where each part is represented as an array of node values. If there are fewer nodes than k, the remaining parts should be empty arrays.

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

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

Explanation: The list has 3 nodes but k=5, so the first 3 parts get one node each, and the last 2 parts are empty.

Constraints

  • The number of nodes in the list is in the range [0, 1000]
  • 0 <= Node.val <= 1000
  • 1 <= k <= 50

Approach

Fast and Slow Pointers pattern

1. Count the Total Length

  • Traverse the entire linked list to count the total number of nodes.
  • This is needed to calculate how to divide the list.

2. Calculate Part Sizes

  • Compute base = Math.floor(length / k) — the minimum number of nodes each part gets.
  • Compute extra = length % k — the number of parts that get one additional node.
  • The first extra parts will have base + 1 nodes, and the remaining parts will have base nodes.

3. Build Each Part

  • Iterate k times to create each part.
  • For each part, determine its size: base + 1 if there are still extra nodes to distribute, otherwise base.
  • Collect that many node values into an array and move the pointer forward.

4. Handle Empty Parts

  • If the list has fewer nodes than k, some parts will have a size of 0, resulting in empty arrays.
  • These are naturally handled since base will be 0 and extra will be exhausted early.

Key Insight

  • The greedy approach of giving the first extra parts one more node ensures the constraint that earlier parts are at most one node longer.
Time
O(n)one pass to count, one pass to split.
Space
O(n)for the output arrays containing all node values.

Visualization

Input:
Linked List Traversal
—
102132null

No animation available

Slow (S)Fast (F)Both
0 steps

Solution Code

Previous
Linked List Components
Next
Remove Duplicates from Sorted List II