Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Split Linked List in Parts solution and explanation

MediumLinked List6 min read70.6% acceptanceUpdated 9 Apr 2026
Asked atAmazonMicrosoftGoogleMetaBloomberg
Practise Split Linked List in Parts
11:01
Split Linked List in Parts - Leetcode 725 - PythonNeetCodeIO · 11:01 · 15K viewsWatch on YouTube
9 more videos on this problem
  1. Split Linked List in Parts - Leetcode 725 - PythonNeetCodeIO · 11:01 · 15K views
  2. Split Linked List in Parts | Clean | Simple Code | Dry Run | Leetcode - 725 | codestorywithMIKcodestorywithMIK · 28:30 · 13K views
  3. LeetCode 725 - Split Linked List in PartsTechBayArea · 17:35 · 1K views
  4. Split Linked List in Parts| Leetcode 725 |C++ |Linked List-Medium |September Daily ChallengeHarsh Patel · 6:49 · 998 views
  5. Split Linked List in Parts Leetcode 725 || Coding Culture5 Minutes Code · 9:00 · 532 views
  6. Leetcode | 725. Split Linked List in Parts | Medium | JavaDeveloper Docs · 6:09 · 365 views
  7. LeetCode 725. Split Linked List in Parts - Amazon Interview QuestionCode with Carter · 4:38 · 332 views
  8. Daily Leetcode #1254: Sep 06, 2023 - 725. Split Linked List in PartsProgramming Live with Larry · 14:37 · 278 views
  9. Daily Leetcode #547: Sep 29, 2021 - 725. Split Linked List in PartsProgramming Live with Larry · 30:24 · 232 views
  10. 725. Split Linked List in Parts | Amazon | Apple | Leetcode medium | DSA buddy | C++ | O(k+m)DSA Buddy · 13:03 · 222 views

The problem

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.

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def splitListToParts(self, root: ListNode, k: int):
        parts = [None] * k
        length = 0
        node = root
        while node:
            length += 1
            node = node.next
        partSize = length // k
        extraNodes = length % k
        node = root
        for i in range(k):
            parts[i] = node
            currentPartSize = partSize + (1 if i < extraNodes else 0)
            for j in range(currentPartSize - 1):
                if node:
                    node = node.next
            if node:
                nextPart = node.next
                node.next = None
                node = nextPart
        return parts
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public ListNode[] splitListToParts(ListNode root, int k) {
    ListNode[] parts = new ListNode[k];
    int length = 0;
    ListNode node = root;
    while (node != null) {
        length++;
        node = node.next;
    }
    int partSize = length / k;
    int extraNodes = length % k;
    node = root;
    for (int i = 0; i < k && node != null; i++) {
        parts[i] = node;
        int currentPartSize = partSize + (i < extraNodes ? 1 : 0);
        for (int j = 1; j < currentPartSize; j++) {
            node = node.next;
        }
        ListNode nextPart = node.next;
        node.next = null;
        node = nextPart;
    }
    return parts;
}
#include <vector>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

std::vector<ListNode*> splitListToParts(ListNode* root, int k) {
    std::vector<ListNode*> parts(k, nullptr);
    int length = 0;
    ListNode* node = root;
    while (node) {
        length++;
        node = node->next;
    }
    int partSize = length / k;
    int extraNodes = length % k;
    node = root;
    for (int i = 0; i < k && node; i++) {
        parts[i] = node;
        int currentSize = partSize + (i < extraNodes ? 1 : 0);
        for (int j = 1; j < currentSize; j++) {
            node = node->next;
        }
        ListNode* nextPart = node->next;
        node->next = nullptr;
        node = nextPart;
    }
    return parts;
}
function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

var splitListToParts = function(root, k) {
    const parts = new Array(k).fill(null);
    let length = 0;
    let node = root;
    while (node) {
        length++;
        node = node.next;
    }
    const partSize = Math.floor(length / k);
    let extraNodes = length % k;
    node = root;
    for (let i = 0; i < k && node; i++) {
        parts[i] = node;
        let currentSize = partSize + (i < extraNodes ? 1 : 0);
        for (let j = 1; j < currentSize; j++) {
            node = node.next;
        }
        let nextPart = node.next;
        node.next = null;
        node = nextPart;
    }
    return parts;
};
#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode** splitListToParts(struct ListNode* root, int k, int* returnSize) {
    struct ListNode** parts = malloc(sizeof(struct ListNode*) * k);
    for (int i = 0; i < k; i++)
        parts[i] = NULL;

    int length = 0;
    struct ListNode* node = root;
    while (node) {
        length++;
        node = node->next;
    }

    int partSize = length / k;
    int extraNodes = length % k;

    node = root;
    for (int i = 0; i < k && node; i++) {
        parts[i] = node;
        int currentPartSize = partSize + (i < extraNodes ? 1 : 0);
        for (int j = 1; j < currentPartSize; j++) {
            node = node->next;
        }
        struct ListNode* nextPart = node->next;
        node->next = NULL;
        node = nextPart;
    }
    *returnSize = k;
    return parts;
}
public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    public ListNode[] SplitListToParts(ListNode root, int k) {
        ListNode[] parts = new ListNode[k];
        int length = 0;
        ListNode node = root;
        while (node != null) {
            length++;
            node = node.next;
        }
        int partSize = length / k;
        int extraNodes = length % k;
        node = root;
        for (int i = 0; i < k && node != null; i++) {
            parts[i] = node;
            int currentSize = partSize + (i < extraNodes ? 1 : 0);
            for (int j = 1; j < currentSize; j++) {
                node = node.next;
            }
            ListNode nextPart = node.next;
            node.next = null;
            node = nextPart;
        }
        return parts;
    }
}

This Python solution follows the same logic: it calculates the length of the linked list, decides on the split sizes for each part, and uses list indexing to store the result. Python’s handling of list operations and iterations makes the code concise.

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.

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def splitListToParts(self, root: ListNode, k: int):
        length = 0
        node = root
        while node:
            length += 1
            node = node.next
        partSize, extra = divmod(length, k)
        parts = [None] * k
        node = root
        for i in range(k):
            head = node
            for j in range(partSize + (i < extra) - 1):
                if node:
                    node = node.next
            if node:
                nextPart = node.next
                node.next = None
                node = nextPart
            parts[i] = head
        return parts
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public ListNode[] splitListToParts(ListNode root, int k) {
    ListNode[] parts = new ListNode[k];
    int length = 0;
    ListNode node = root;
    while (node != null) {
        length++;
        node = node.next;
    }
    int partSize = length / k, extraNodes = length % k;
    node = root;
    for (int i = 0; i < k && node != null; i++) {
        parts[i] = node;
        int currentPartSize = partSize + (i < extraNodes ? 1 : 0);
        for (int j = 1; j < currentPartSize; j++) {
            node = node.next;
        }
        if (node != null) {
            ListNode nextPart = node.next;
            node.next = null;
            node = nextPart;
        }
    }
    return parts;
}
#include <vector>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

std::vector<ListNode*> splitListToParts(ListNode* root, int k) {
    std::vector<ListNode*> parts(k, nullptr);
    int length = 0;
    ListNode* node = root;
    while (node) ++length, node = node->next;
    int partSize = length / k, extraNodes = length % k;
    node = root;
    for (int i = 0; i < k && node; ++i) {
        parts[i] = node;
        int currentSize = partSize + (i < extraNodes);
        for (int j = 1; j < currentSize; ++j) node = node->next;
        if (node) {
            ListNode* nextPart = node->next;
            node->next = nullptr;
            node = nextPart;
        }
    }
    return parts;
}
function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

var splitListToParts = function(root, k) {
    const parts = new Array(k).fill(null);
    let length = 0;
    let node = root;
    while (node) {
        length++;
        node = node.next;
    }
    const partSize = Math.floor(length / k);
    let extraNodes = length % k;
    node = root;
    for (let i = 0; i < k && node; i++) {
        parts[i] = node;
        let currentSize = partSize + (i < extraNodes ? 1 : 0);
        for (let j = 1; j < currentSize; j++) node = node.next;
        if (node) {
            const nextPart = node.next;
            node.next = null;
            node = nextPart;
        }
    }
    return parts;
};
#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode** splitListToParts(struct ListNode* root, int k, int* returnSize) {
    struct ListNode** parts = malloc(sizeof(struct ListNode*) * k);
    for (int i = 0; i < k; i++)
        parts[i] = NULL;

    int length = 0;
    struct ListNode* node = root;
    while (node) {
        length++;
        node = node->next;
    }

    int partSize = length / k, extraNodes = length % k;
    node = root;
    for (int i = 0; i < k && node; i++) {
        parts[i] = node;
        int currentPartSize = partSize + (i < extraNodes);
        for (int j = 1; j < currentPartSize; j++) {
            node = node->next;
        }
        if (node) {
            struct ListNode* nextPart = node->next;
            node->next = NULL;
            node = nextPart;
        }
    }
    *returnSize = k;
    return parts;
}
public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    public ListNode[] SplitListToParts(ListNode root, int k) {
        ListNode[] parts = new ListNode[k];
        int length = 0;
        ListNode node = root;
        while (node != null) {
            length++;
            node = node.next;
        }
        int partSize = length / k, extraNodes = length % k;
        node = root;
        for (int i = 0; i < k && node != null; i++) {
            parts[i] = node;
            int currentSize = partSize + (i < extraNodes);
            for (int j = 1; j < currentSize; j++) {
                node = node.next;
            }
            if (node != null) {
                ListNode nextPart = node.next;
                node.next = null;
                node = nextPart;
            }
        }
        return parts;
    }
}

This Python solution combines looping and splitting in one traversal of the linked list. The use of divmod simplifies the calculation of base size and extra nodes needed, achieving a concise solution for the node management.

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 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.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function splitListToParts(head: ListNode | null, k: number): Array<ListNode | null> {
    let n = 0;
    for (let cur = head; cur !== null; cur = cur.next) {
        n++;
    }
    const cnt = (n / k) | 0;
    const mod = n % k;
    const ans: Array<ListNode | null> = Array(k).fill(null);
    let cur = head;
    for (let i = 0; i < k && cur !== null; i++) {
        ans[i] = cur;
        let m = cnt + (i < mod ? 1 : 0);
        for (let j = 1; j < m; j++) {
            cur = cur.next!;
        }
        let next = cur.next;
        cur.next = null;
        cur = next;
    }
    return ans;
}
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func splitListToParts(head *ListNode, k int) []*ListNode {
	n := 0
	for cur := head; cur != nil; cur = cur.Next {
		n++
	}

	cnt := n / k
	mod := n % k
	ans := make([]*ListNode, k)
	cur := head

	for i := 0; i < k && cur != nil; i++ {
		ans[i] = cur
		m := cnt
		if i < mod {
			m++
		}
		for j := 1; j < m; j++ {
			cur = cur.Next
		}
		next := cur.Next
		cur.Next = nil
		cur = next
	}

	return ans
}
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 parts.

Simulation–

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.

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.

Comments

Next problem · similarRotate ListMedium
Now write it yourselfClose this page and solve Split Linked List in Parts in the editor, without looking.
Practise Split Linked List in Parts