#725

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Split Linked List in Parts

Efficiently split a singly linked list into k consecutive parts, balancing sizes while preserving the original node order.

linked list

Problem Statement

Given the head of a singly linked list and an integer k, divide the list into k consecutive parts. Each part should have a length as close as possible, ensuring no two parts differ in size by more than one, with earlier parts being at least as long as later ones.

Return an array of the k parts in the order they appear in the original list. Some parts may be null if the number of nodes is less than k. Maintain node connections accurately to preserve linked list integrity.

Examples

Example 1

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

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

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

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

Solution Approach

Compute Sizes for Each Part

Traverse the list once to count total nodes N. Compute the minimum size for each part as N / k and distribute the remainder N % k among the first parts, ensuring proper size balancing.

Split with Pointer Manipulation

Iterate through the linked list, for each part walk the required number of nodes, then disconnect the next pointer to isolate the part. Keep track of current node to start the next part seamlessly.

Construct Result Array

Store the head of each split part in an array of length k. If nodes run out before filling all parts, assign null to remaining array slots, preserving order and size rules.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(1)

Time complexity is O(N) because each node is visited exactly once. Space complexity is O(1) aside from the output array, as the algorithm only manipulates pointers without allocating extra lists.

What Interviewers Usually Probe

Check if the candidate correctly handles empty nodes and k larger than list length.
Watch for proper pointer disconnection to avoid cycles or shared references between parts.
Look for correct distribution of extra nodes to the first N % k parts for balanced sizing.

Common Pitfalls or Variants

Common pitfalls

Failing to account for N % k extra nodes can lead to uneven part sizes.
Incorrectly reconnecting next pointers may merge parts or corrupt the list.
Returning parts out of order instead of preserving the original sequence.

Follow-up variants

Split into parts but return sizes instead of the actual sublists for a memory-efficient check.
Split a doubly linked list maintaining both next and previous pointers correctly.
Split linked list in parts with additional constraint that no part can be empty unless necessary.

FAQ

What is the most efficient way to split a linked list into k parts?

Count the nodes, compute base size and extra nodes, then iterate with pointer disconnection to form each part in O(N) time.

Why do some parts become null in Split Linked List in Parts?

If k is greater than the number of nodes, extra parts have no nodes, so they are represented as null to satisfy the k-length output array.

How do I handle the remainder nodes when dividing the list?

Distribute the first N % k nodes, adding one extra node to the initial parts so that no two parts differ in size by more than one.

Can this method be adapted for doubly linked lists?

Yes, but you must adjust both next and previous pointers when splitting each part to maintain list integrity.

What is the key failure mode in pointer manipulation for this problem?

Incorrectly updating next pointers can merge parts or leave cycles, so carefully disconnect each part at the correct node.

terminal

Solution

Solution 1: Simulation

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def splitListToParts(
        self, head: Optional[ListNode], k: int
    ) -> List[Optional[ListNode]]:
        n = 0
        cur = head
        while cur:
            n += 1
            cur = cur.next
        cnt, mod = divmod(n, k)
        ans = [None] * k
        cur = head
        for i in range(k):
            if cur is None:
                break
            ans[i] = cur
            m = cnt + int(i < mod)
            for _ in range(1, m):
                cur = cur.next
            nxt = cur.next
            cur.next = None
            cur = nxt
        return ans

Continue Practicing

#707 design linked list #706 design hashmap #705 design hashset