Skip to main content
Talentd

Split Linked List in Parts - Solution & Explanation

MediumLinked List20 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

Given the head of a singly linked list and an integer k, 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 one. This may lead to some parts being null.

The parts should be in the 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 the k parts.

 

Example 1:

Input: head = [1,2,3], k = 5
Output: [[1],[2],[3],[],[]]
Explanation:
The first element output[0] has output[0].val = 1, output[0].next = null.
The last element output[4] is null, but its string representation as a ListNode is [].

Example 2:

Input: head = [1,2,3,4,5,6,7,8,9,10], k = 3
Output: [[1,2,3,4],[5,6,7],[8,9,10]]
Explanation:
The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.

 

Constraints:

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

Approach Overview

Problem Overview: You are given the head of a singly linked list and an integer k. The task is to split the list into k consecutive parts such that the sizes differ by at most one node. Earlier parts must be larger when the nodes cannot be divided evenly. Each part should remain a valid linked list after splitting.

Approach 1: Calculate Length and Split (O(n) time, O(1) space)

Start by traversing the list once to compute its total length n. The base size of each part becomes n / k, and the first n % k parts receive one extra node. Iterate through the list again and detach segments accordingly. For each part, move a pointer partSize steps, keep track of the previous node, and set prev.next = null to terminate that sublist.

This method works because you know the exact size of every part before performing the split. It requires only two linear passes over the list and constant extra memory. The technique relies heavily on pointer manipulation, which is a fundamental pattern when working with linked list problems.

Approach 2: Iterative Splitting with Modification (O(n) time, O(1) space)

This variation also begins by determining the total length of the list. Instead of computing all sizes up front, the algorithm dynamically adjusts the size of each segment while iterating. Track the remaining nodes and remaining parts. For each step, calculate the current part size using remainingNodes / remainingParts and distribute an extra node when necessary.

Traverse exactly that many nodes, detach the segment, and update counters for the remaining list. This approach modifies the list progressively and avoids storing intermediate sizes in an array. It still performs a single pass for length and another for splitting, keeping the runtime O(n) with constant extra space.

Both strategies rely on careful pointer updates and controlled traversal. Problems like this appear frequently when manipulating list structure, especially in tasks involving segmentation, partitioning, or re-linking nodes within a linked list.

Recommended for interviews: The length calculation approach is the one most interviewers expect. It clearly demonstrates that you can derive part sizes mathematically using n / k and n % k, then apply precise pointer manipulation to split the list. Showing the reasoning behind equal distribution first demonstrates problem understanding, while the clean O(n) implementation shows practical coding skill.

Approach 1: Calculate Length and Split

This approach involves two main steps. First, traverse the linked list to determine its length. Then, decide how to split this length evenly across the k parts. Calculate the base size for each part and determine how many parts need an extra node.

The solution first calculates the total length of the linked list. Using this information, it determines the base size that each part should have and how many of the initial parts should receive an extra node due to the remainder from the division of length by k. It then iterates through the linked list, splitting it into the desired parts by adjusting the next pointers appropriately.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) where n is the length of the linked list.
Space Complexity: O(k) for storing the resulting list parts.

Try this approach in the editor →

Approach 2: Iterative Splitting with Modification

This approach involves iterating through the linked list and modifying the pointers to split the list directly into parts of calculated sizes based on total length and k. It ensures that the list splitting does not require additional passes, combining calculation and splitting in a single traversal.

This C solution simplifies the approach by combining the length calculation and direct list splitting into one step. By iterating and breaking the list dynamically, this technique ensures efficiency in handling the linked list pointers.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) where n is the length of the linked list.
Space Complexity: O(k) for storing the resulting list pointers.

Try this approach in the editor →

Approach 3: Simulation

First, we traverse the linked list to obtain its length n, and then we calculate the average length cnt = \lfloor \frac{n}{k} \rfloor and the remainder mod = n bmod k. For the first mod parts, each part has a length of cnt + 1, while the lengths of the remaining parts are cnt.

Next, we just need to traverse the linked list and split it into k parts.

The time complexity is O(n), and the space complexity is O(k). Here, n is the length of the linked list.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Calculate Length and Split

Time Complexity: O(n) where n is the length of the linked list.
Space Complexity: O(k) for storing the resulting list parts.

Iterative Splitting with Modification

Time Complexity: O(n) where n is the length of the linked list.
Space Complexity: O(k) for storing the resulting list pointers.

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Calculate Length and SplitO(n)O(1)Best general solution. Easy to reason about part sizes using n/k and remainder distribution.
Iterative Splitting with ModificationO(n)O(1)Useful when computing sizes dynamically while traversing and modifying the list.

Video Solution

Split Linked List in Parts - Leetcode 725 - Python • NeetCodeIO • 15,935 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Split Linked List in Parts easy or hard?
Split Linked List in Parts is considered a medium difficulty problem. The main challenge is correctly distributing nodes across k parts while maintaining valid linked list structures and handling cases where the list has fewer nodes than k.
Split Linked List in Parts Python/Java solution
Python and Java implementations follow the same logic: compute the list length, determine the size of each part, and iterate through the list to detach segments. The algorithm uses simple pointer traversal and runs in O(n) time with constant extra memory.
How to solve Split Linked List in Parts in O(n)?
First traverse the linked list to count the number of nodes. Compute the base part size using n / k and determine how many parts need an extra node using n % k. Iterate through the list again, cutting the list after the required number of nodes for each part by setting the previous node's next pointer to null.
What is the best approach for Split Linked List in Parts?
The best approach calculates the total length of the linked list first, then determines the base size of each part using n / k and distributes the remaining nodes using n % k. After that, iterate through the list and detach each segment by adjusting next pointers. This runs in O(n) time and O(1) extra space.
Is Split Linked List in Parts asked at Google/Amazon/Meta?
Linked list partitioning and structural manipulation problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variants of splitting or restructuring linked lists test pointer manipulation, traversal logic, and edge case handling.
What data structure is used in Split Linked List in Parts?
The problem uses a singly linked list. The solution focuses on pointer traversal, node counting, and modifying next references to break the list into independent segments.
What is the time complexity of Split Linked List in Parts?
The optimal solution runs in O(n) time where n is the number of nodes in the list. One pass computes the total length and another pass splits the list into k parts. The space complexity is O(1) excluding the output array of list heads.

Ready to solve this problem?

Practice Split Linked List in Parts with our built-in code editor and test cases.

Practice on FleetCode
Previous

Odd Even Linked List

Next

Rotate List