Split Linked List in Parts - Practice Coding Problems

Split Linked List in Parts - Problem

Linked List Medium

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.

Input & Output

Example 1 — Basic Split

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

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

💡 Note: Length 3 split into 5 parts: first 3 parts get 1 node each, last 2 parts are empty

Example 2 — Even Distribution

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

💡 Note: Length 10 split into 3 parts: base size 3, remainder 1, so first part gets 4 nodes

Example 3 — Single Node

$ Input: head = [1], k = 1

› Output: [[1]]

💡 Note: Single node in single part

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Linked list [1,2,3,4,5] and k=3

Calculate

Length=5, base=1, remainder=2 → sizes [2,2,1]

Split

Break connections to create [[1,2], [3,4], [5]]

Key Takeaway

🎯 Key Insight: First (remainder) parts get one extra node when length doesn't divide evenly

Asked in

F Facebook 15 M Microsoft 12 a Amazon 8

The key insight is to distribute the extra nodes (remainder) to the first few parts when the list length doesn't divide evenly by k. Best approach is the two-pass method: count nodes first, then split based on calculated sizes. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Two-Pass: Count Then Split	O(n)	O(1)	First pass counts nodes, second pass splits based on calculated sizes
Single Pass Split	O(n)	O(1)	Calculate sizes on-the-fly and split in one traversal

Two-Pass: Count Then Split — Algorithm Steps

Step 1: Traverse the list to count total nodes
Step 2: Calculate base size and remainder for distribution
Step 3: Split the list by breaking connections at calculated positions

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Nodes

Traverse list to count total length

Calculate Sizes

Determine how many nodes each part gets

Split List

Break connections at calculated positions

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

struct ListNode** solution(struct ListNode* head, int k, int* returnSize) {
    *returnSize = k;
    
    // Count total nodes
    int length = 0;
    struct ListNode* curr = head;
    while (curr) {
        length++;
        curr = curr->next;
    }
    
    // Calculate base size and remainder
    int baseSize = length / k;
    int remainder = length % k;
    
    struct ListNode** result = (struct ListNode**)malloc(k * sizeof(struct ListNode*));
    curr = head;
    
    for (int i = 0; i < k; i++) {
        if (!curr) {
            result[i] = NULL;
            continue;
        }
        
        // First 'remainder' parts get one extra node
        int partSize = baseSize + (i < remainder ? 1 : 0);
        
        if (partSize == 0) {
            result[i] = NULL;
            continue;
        }
        
        struct ListNode* partHead = curr;
        // Move to the end of current part
        for (int j = 0; j < partSize - 1; j++) {
            curr = curr->next;
        }
        
        // Break the connection
        struct ListNode* nextPart = curr->next;
        curr->next = NULL;
        curr = nextPart;
        
        result[i] = partHead;
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Parse array input
    struct ListNode* head = NULL;
    if (strcmp(line, "[]") != 0) {
        // Simple parsing for [1,2,3,4,5] format
        char* ptr = line + 1; // Skip '['
        struct ListNode* tail = NULL;
        
        while (*ptr && *ptr != ']') {
            int val = 0;
            while (*ptr && (*ptr < '0' || *ptr > '9')) ptr++;
            while (*ptr && *ptr >= '0' && *ptr <= '9') {
                val = val * 10 + (*ptr - '0');
                ptr++;
            }
            
            struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
            node->val = val;
            node->next = NULL;
            
            if (!head) {
                head = tail = node;
            } else {
                tail->next = node;
                tail = node;
            }
        }
    }
    
    int k;
    scanf("%d", &k);
    
    int returnSize;
    struct ListNode** result = solution(head, k, &returnSize);
    
    // Format output
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("[");
        struct ListNode* curr = result[i];
        int first = 1;
        while (curr) {
            if (!first) printf(",");
            printf("%d", curr->val);
            curr = curr->next;
            first = 0;
        }
        printf("]");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Two passes through the list: O(n) to count + O(n) to split = O(n)

✓ Linear Growth

Space Complexity

O(1)

Only uses constant extra space for variables, result array doesn't count

✓ Linear Space

28.4K Views

Medium Frequency

~15 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two-Pass: Count Then Split — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler