Split Linked List in Parts

🎯

Split Linked List in Parts

mediumTWO_POINTERGoogleAmazon

Imagine you have a long chain of packages that need to be delivered evenly among several trucks, but some trucks might get one extra package if the packages don't divide evenly.

💡 This problem involves splitting a linked list into k parts as evenly as possible. Beginners often struggle with how to handle the remainder when the list size isn't divisible by k, and how to split the list without losing nodes or corrupting links.

📋

Problem Statement

Given the head of a singly linked list and an integer k, split the linked list into k consecutive 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 if the list has fewer nodes than k. Return an array of the k parts' heads.

1 ≤ number of nodes in linked list ≤ 10^51 ≤ k ≤ 50

💡

Example

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

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

The list has 3 nodes but k=5, so the first 3 parts have one node each, and the last two parts are empty.

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 list size is 10, divided into 3 parts: first part has 4 nodes, next two have 3 nodes each.

• k equals the length of the list → each part has exactly one node
• k greater than the length of the list → some parts are empty
• list with only one node and k > 1 → first part has one node, rest empty
• list is empty (head = null) and k > 0 → all parts are empty

⚠️

Common Mistakes

Not handling remainder correctly

Parts sizes differ by more than one, violating problem constraints

✅ Always assign one extra node to the first 'remainder' parts

Not breaking the link after each part

Parts remain connected, causing incorrect output or infinite loops

✅ Set current.next = None (or null) after finishing each part

Accessing current.next without checking if current is null

Runtime error or null pointer exception

✅ Always check if current is not null before accessing current.next

Returning fewer than k parts when k > list length

Output array size is incorrect, failing test cases

✅ Always return an array of size k, filling empty parts with null

🧠

Brute Force (Count and Split with Multiple Passes)

💡 This approach is straightforward and helps beginners understand the problem by breaking it down into simple steps, even if it is not the most efficient.

Intuition

First, count the total number of nodes. Then, calculate the size of each part and the remainder. Finally, iterate through the list multiple times to split it into parts accordingly.

Algorithm

1. Traverse the linked list to count the total number of nodes.
2. Calculate the base size of each part as total_nodes // k and the remainder as total_nodes % k.
3. For each part, assign base size plus one extra node if remainder is still positive, then decrement remainder.
4. Traverse the list again to cut the list into parts of the calculated sizes and store their heads.

💡 The challenge is to carefully track the sizes and correctly break the links to form separate parts without losing nodes.

</>

Code

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

def splitListToParts(head, k):
    # Step 1: Count total nodes
    total_nodes = 0
    current = head
    while current:
        total_nodes += 1
        current = current.next

    # Step 2: Calculate size and remainder
    part_size = total_nodes // k
    remainder = total_nodes % k

    parts = []
    current = head

    # Step 3: Split the list
    for i in range(k):
        head_part = current
        size = part_size + (1 if remainder > 0 else 0)
        if remainder > 0:
            remainder -= 1

        # Step 4: Move current pointer size-1 times
        for j in range(size - 1):
            if current:
                current = current.next

        # Cut the list if needed
        if current:
            next_part = current.next
            current.next = None
            current = next_part

        parts.append(head_part)

    return parts

# Driver code to test
if __name__ == '__main__':
    # Helper to create linked list
    def create_linked_list(arr):
        dummy = ListNode(0)
        curr = dummy
        for val in arr:
            curr.next = ListNode(val)
            curr = curr.next
        return dummy.next

    head = create_linked_list([1,2,3,4,5,6,7,8,9,10])
    k = 3
    parts = splitListToParts(head, k)
    for part in parts:
        vals = []
        while part:
            vals.append(part.val)
            part = part.next
        print(vals)

Line Notes

total_nodes = 0Initialize counter to count nodes in the list

while current:Traverse entire list to get total length

part_size = total_nodes // kCalculate minimum size each part should have

remainder = total_nodes % kCalculate how many parts get an extra node

for i in range(k):Iterate over each part to build it

size = part_size + (1 if remainder > 0 else 0)Assign extra node to first 'remainder' parts

if remainder > 0: remainder -= 1Decrease remainder after assigning extra node

for j in range(size - 1):Move pointer to the last node of current part

current.next = NoneBreak the link to separate current part from the rest

parts.append(head_part)Add head of current part to result list

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        int totalNodes = 0;
        ListNode current = head;
        // Count total nodes
        while (current != null) {
            totalNodes++;
            current = current.next;
        }

        int partSize = totalNodes / k;
        int remainder = totalNodes % k;

        ListNode[] parts = new ListNode[k];
        current = head;

        for (int i = 0; i < k; i++) {
            ListNode headPart = current;
            int size = partSize + (remainder > 0 ? 1 : 0);
            if (remainder > 0) remainder--;

            for (int j = 0; j < size - 1; j++) {
                if (current != null) current = current.next;
            }

            if (current != null) {
                ListNode nextPart = current.next;
                current.next = null;
                current = nextPart;
            }

            parts[i] = headPart;
        }

        return parts;
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        ListNode head = new ListNode(1);
        ListNode curr = head;
        for (int i = 2; i <= 10; i++) {
            curr.next = new ListNode(i);
            curr = curr.next;
        }
        ListNode[] parts = sol.splitListToParts(head, 3);
        for (ListNode part : parts) {
            ListNode temp = part;
            System.out.print("[");
            while (temp != null) {
                System.out.print(temp.val);
                temp = temp.next;
                if (temp != null) System.out.print(",");
            }
            System.out.println("]");
        }
    }
}

Line Notes

int totalNodes = 0;Initialize node count

while (current != null)Count total nodes in list

int partSize = totalNodes / k;Calculate base size of each part

int remainder = totalNodes % k;Calculate how many parts get an extra node

for (int i = 0; i < k; i++)Loop over each part to build it

int size = partSize + (remainder > 0 ? 1 : 0);Assign extra node to first remainder parts

if (remainder > 0) remainder--;Decrement remainder after assigning extra node

for (int j = 0; j < size - 1; j++)Move pointer to last node of current part

current.next = null;Break link to separate current part

parts[i] = headPart;Store head of current part

#include <iostream>
#include <vector>
using namespace std;

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

class Solution {
public:
    vector<ListNode*> splitListToParts(ListNode* head, int k) {
        int totalNodes = 0;
        ListNode* current = head;
        // Count total nodes
        while (current) {
            totalNodes++;
            current = current->next;
        }

        int partSize = totalNodes / k;
        int remainder = totalNodes % k;

        vector<ListNode*> parts(k, nullptr);
        current = head;

        for (int i = 0; i < k; i++) {
            ListNode* headPart = current;
            int size = partSize + (remainder > 0 ? 1 : 0);
            if (remainder > 0) remainder--;

            for (int j = 0; j < size - 1; j++) {
                if (current) current = current->next;
            }

            if (current) {
                ListNode* nextPart = current->next;
                current->next = nullptr;
                current = nextPart;
            }

            parts[i] = headPart;
        }

        return parts;
    }
};

// Helper to create linked list
ListNode* createLinkedList(const vector<int>& vals) {
    ListNode dummy(0);
    ListNode* curr = &dummy;
    for (int v : vals) {
        curr->next = new ListNode(v);
        curr = curr->next;
    }
    return dummy.next;
}

// Helper to print parts
void printParts(const vector<ListNode*>& parts) {
    for (auto part : parts) {
        cout << "[";
        ListNode* curr = part;
        while (curr) {
            cout << curr->val;
            curr = curr->next;
            if (curr) cout << ",";
        }
        cout << "]\n";
    }
}

int main() {
    Solution sol;
    ListNode* head = createLinkedList({1,2,3,4,5,6,7,8,9,10});
    int k = 3;
    vector<ListNode*> parts = sol.splitListToParts(head, k);
    printParts(parts);
    return 0;
}

Line Notes

int totalNodes = 0;Initialize count of nodes

while (current)Traverse list to count nodes

int partSize = totalNodes / k;Calculate base size per part

int remainder = totalNodes % k;Calculate how many parts get extra node

for (int i = 0; i < k; i++)Loop over each part to build

int size = partSize + (remainder > 0 ? 1 : 0);Assign extra node to first remainder parts

if (remainder > 0) remainder--;Decrement remainder after assignment

for (int j = 0; j < size - 1; j++)Move pointer to last node of current part

current->next = nullptr;Break link to separate current part

parts[i] = headPart;Store head of current part

function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

function splitListToParts(head, k) {
    let totalNodes = 0;
    let current = head;
    // Count total nodes
    while (current !== null) {
        totalNodes++;
        current = current.next;
    }

    let partSize = Math.floor(totalNodes / k);
    let remainder = totalNodes % k;

    const parts = new Array(k).fill(null);
    current = head;

    for (let i = 0; i < k; i++) {
        let headPart = current;
        let size = partSize + (remainder > 0 ? 1 : 0);
        if (remainder > 0) remainder--;

        for (let j = 0; j < size - 1; j++) {
            if (current !== null) current = current.next;
        }

        if (current !== null) {
            let nextPart = current.next;
            current.next = null;
            current = nextPart;
        }

        parts[i] = headPart;
    }

    return parts;
}

// Helper to create linked list
function createLinkedList(arr) {
    let dummy = new ListNode(0);
    let curr = dummy;
    for (let val of arr) {
        curr.next = new ListNode(val);
        curr = curr.next;
    }
    return dummy.next;
}

// Test
const head = createLinkedList([1,2,3,4,5,6,7,8,9,10]);
const k = 3;
const parts = splitListToParts(head, k);
for (const part of parts) {
    let vals = [];
    let curr = part;
    while (curr !== null) {
        vals.push(curr.val);
        curr = curr.next;
    }
    console.log(vals);
}

Line Notes

let totalNodes = 0;Initialize node count

while (current !== null)Traverse list to count nodes

let partSize = Math.floor(totalNodes / k);Calculate base size per part

let remainder = totalNodes % k;Calculate how many parts get extra node

for (let i = 0; i < k; i++)Loop over each part to build

let size = partSize + (remainder > 0 ? 1 : 0);Assign extra node to first remainder parts

if (remainder > 0) remainder--;Decrement remainder after assignment

for (let j = 0; j < size - 1; j++)Move pointer to last node of current part

current.next = null;Break link to separate current part

parts[i] = headPart;Store head of current part

⏱

Complexity

TimeO(n + k)

SpaceO(k) for output array

We traverse the list once to count nodes (O(n)) and once more to split into parts (O(n)). The output array has size k.

💡 For n=100 and k=5, we do about 200 steps plus 5 for output, which is efficient enough for interviews.

Interview Verdict: Accepted

This approach is simple and accepted, but can be improved by combining counting and splitting in one pass.

🧠

One-Pass Split Using Precomputed Sizes

💡 This approach improves efficiency by combining counting and splitting into a single pass after counting, reducing redundant traversals.

Intuition

Count the total nodes first, then compute the size of each part. Then traverse the list once more, splitting parts on the fly without nested loops.

Algorithm

1. Count total nodes in the list.
2. Calculate base size and remainder for parts.
3. Iterate through the list once, for each part move exactly the required number of nodes.
4. Break the link after the last node of each part and store the head.

💡 This approach is easier to implement correctly and avoids multiple traversals for each part.

</>

Code

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

def splitListToParts(head, k):
    total_nodes = 0
    current = head
    while current:
        total_nodes += 1
        current = current.next

    part_size = total_nodes // k
    remainder = total_nodes % k

    parts = []
    current = head

    for i in range(k):
        head_part = current
        size = part_size + (1 if remainder > 0 else 0)
        if remainder > 0:
            remainder -= 1

        for j in range(size - 1):
            if current:
                current = current.next

        if current:
            next_part = current.next
            current.next = None
            current = next_part

        parts.append(head_part)

    return parts

# Driver code
if __name__ == '__main__':
    def create_linked_list(arr):
        dummy = ListNode(0)
        curr = dummy
        for val in arr:
            curr.next = ListNode(val)
            curr = curr.next
        return dummy.next

    head = create_linked_list([1,2,3,4,5,6,7,8,9,10])
    k = 3
    parts = splitListToParts(head, k)
    for part in parts:
        vals = []
        while part:
            vals.append(part.val)
            part = part.next
        print(vals)

Line Notes

total_nodes = 0Initialize counter for total nodes

while current:Count nodes in one pass

part_size = total_nodes // kCalculate base size per part

remainder = total_nodes % kCalculate how many parts get an extra node

for i in range(k):Iterate over each part

size = part_size + (1 if remainder > 0 else 0)Assign extra node to first remainder parts

if remainder > 0: remainder -= 1Decrement remainder after assignment

for j in range(size - 1):Move pointer to last node of current part

current.next = NoneBreak link to separate current part

parts.append(head_part)Add head of current part to result

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        int totalNodes = 0;
        ListNode current = head;
        while (current != null) {
            totalNodes++;
            current = current.next;
        }

        int partSize = totalNodes / k;
        int remainder = totalNodes % k;

        ListNode[] parts = new ListNode[k];
        current = head;

        for (int i = 0; i < k; i++) {
            ListNode headPart = current;
            int size = partSize + (remainder > 0 ? 1 : 0);
            if (remainder > 0) remainder--;

            for (int j = 0; j < size - 1; j++) {
                if (current != null) current = current.next;
            }

            if (current != null) {
                ListNode nextPart = current.next;
                current.next = null;
                current = nextPart;
            }

            parts[i] = headPart;
        }

        return parts;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        ListNode head = new ListNode(1);
        ListNode curr = head;
        for (int i = 2; i <= 10; i++) {
            curr.next = new ListNode(i);
            curr = curr.next;
        }
        ListNode[] parts = sol.splitListToParts(head, 3);
        for (ListNode part : parts) {
            ListNode temp = part;
            System.out.print("[");
            while (temp != null) {
                System.out.print(temp.val);
                temp = temp.next;
                if (temp != null) System.out.print(",");
            }
            System.out.println("]");
        }
    }
}

Line Notes

int totalNodes = 0;Initialize node count

while (current != null)Count nodes in one pass

int partSize = totalNodes / k;Calculate base size per part

int remainder = totalNodes % k;Calculate remainder for extra nodes

for (int i = 0; i < k; i++)Iterate over each part

int size = partSize + (remainder > 0 ? 1 : 0);Assign extra node to first remainder parts

if (remainder > 0) remainder--;Decrement remainder after assignment

for (int j = 0; j < size - 1; j++)Move pointer to last node of current part

current.next = null;Break link to separate current part

parts[i] = headPart;Store head of current part

#include <iostream>
#include <vector>
using namespace std;

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

class Solution {
public:
    vector<ListNode*> splitListToParts(ListNode* head, int k) {
        int totalNodes = 0;
        ListNode* current = head;
        while (current) {
            totalNodes++;
            current = current->next;
        }

        int partSize = totalNodes / k;
        int remainder = totalNodes % k;

        vector<ListNode*> parts(k, nullptr);
        current = head;

        for (int i = 0; i < k; i++) {
            ListNode* headPart = current;
            int size = partSize + (remainder > 0 ? 1 : 0);
            if (remainder > 0) remainder--;

            for (int j = 0; j < size - 1; j++) {
                if (current) current = current->next;
            }

            if (current) {
                ListNode* nextPart = current->next;
                current->next = nullptr;
                current = nextPart;
            }

            parts[i] = headPart;
        }

        return parts;
    }
};

ListNode* createLinkedList(const vector<int>& vals) {
    ListNode dummy(0);
    ListNode* curr = &dummy;
    for (int v : vals) {
        curr->next = new ListNode(v);
        curr = curr->next;
    }
    return dummy.next;
}

void printParts(const vector<ListNode*>& parts) {
    for (auto part : parts) {
        cout << "[";
        ListNode* curr = part;
        while (curr) {
            cout << curr->val;
            curr = curr->next;
            if (curr) cout << ",";
        }
        cout << "]\n";
    }
}

int main() {
    Solution sol;
    ListNode* head = createLinkedList({1,2,3,4,5,6,7,8,9,10});
    int k = 3;
    vector<ListNode*> parts = sol.splitListToParts(head, k);
    printParts(parts);
    return 0;
}

Line Notes

int totalNodes = 0;Initialize node count

while (current)Count nodes in one pass

int partSize = totalNodes / k;Calculate base size per part

int remainder = totalNodes % k;Calculate remainder for extra nodes

for (int i = 0; i < k; i++)Iterate over each part

int size = partSize + (remainder > 0 ? 1 : 0);Assign extra node to first remainder parts

if (remainder > 0) remainder--;Decrement remainder after assignment

for (int j = 0; j < size - 1; j++)Move pointer to last node of current part

current->next = nullptr;Break link to separate current part

parts[i] = headPart;Store head of current part

function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

function splitListToParts(head, k) {
    let totalNodes = 0;
    let current = head;
    while (current !== null) {
        totalNodes++;
        current = current.next;
    }

    let partSize = Math.floor(totalNodes / k);
    let remainder = totalNodes % k;

    const parts = new Array(k).fill(null);
    current = head;

    for (let i = 0; i < k; i++) {
        let headPart = current;
        let size = partSize + (remainder > 0 ? 1 : 0);
        if (remainder > 0) remainder--;

        for (let j = 0; j < size - 1; j++) {
            if (current !== null) current = current.next;
        }

        if (current !== null) {
            let nextPart = current.next;
            current.next = null;
            current = nextPart;
        }

        parts[i] = headPart;
    }

    return parts;
}

function createLinkedList(arr) {
    let dummy = new ListNode(0);
    let curr = dummy;
    for (let val of arr) {
        curr.next = new ListNode(val);
        curr = curr.next;
    }
    return dummy.next;
}

const head = createLinkedList([1,2,3,4,5,6,7,8,9,10]);
const k = 3;
const parts = splitListToParts(head, k);
for (const part of parts) {
    let vals = [];
    let curr = part;
    while (curr !== null) {
        vals.push(curr.val);
        curr = curr.next;
    }
    console.log(vals);
}

Line Notes

let totalNodes = 0;Initialize node count

while (current !== null)Count nodes in one pass

let partSize = Math.floor(totalNodes / k);Calculate base size per part

let remainder = totalNodes % k;Calculate remainder for extra nodes

for (let i = 0; i < k; i++)Iterate over each part

let size = partSize + (remainder > 0 ? 1 : 0);Assign extra node to first remainder parts

if (remainder > 0) remainder--;Decrement remainder after assignment

for (let j = 0; j < size - 1; j++)Move pointer to last node of current part

current.next = null;Break link to separate current part

parts[i] = headPart;Store head of current part

⏱

Complexity

TimeO(n + k)

SpaceO(k) for output array

Counting nodes is O(n), splitting is O(n), and output array size is k.

💡 This approach is efficient for large lists and avoids repeated traversals.

Interview Verdict: Accepted

This is the standard approach to this problem and is optimal in time complexity.

🧠

Optimized One-Pass with Preallocation and Inline Splitting

💡 This approach is a clean, production-ready implementation that combines counting and splitting with minimal overhead and clear code structure.

Intuition

After counting nodes and computing sizes, allocate the result array upfront and split the list inline while iterating, minimizing pointer operations and improving readability.

Algorithm

1. Count the total number of nodes in the linked list.
2. Compute the base size and remainder for the parts.
3. Initialize an array of size k to hold the parts.
4. Iterate through the list, splitting parts inline by moving pointers and breaking links.

💡 This approach balances clarity and efficiency, making it ideal for interviews.

</>

Code

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

def splitListToParts(head, k):
    total_nodes = 0
    current = head
    while current:
        total_nodes += 1
        current = current.next

    part_size = total_nodes // k
    remainder = total_nodes % k

    parts = [None] * k
    current = head

    for i in range(k):
        parts[i] = current
        size = part_size + (1 if remainder > 0 else 0)
        if remainder > 0:
            remainder -= 1

        for j in range(size - 1):
            if current:
                current = current.next

        if current:
            next_part = current.next
            current.next = None
            current = next_part

    return parts

# Driver code
if __name__ == '__main__':
    def create_linked_list(arr):
        dummy = ListNode(0)
        curr = dummy
        for val in arr:
            curr.next = ListNode(val)
            curr = curr.next
        return dummy.next

    head = create_linked_list([1,2,3,4,5,6,7,8,9,10])
    k = 3
    parts = splitListToParts(head, k)
    for part in parts:
        vals = []
        while part:
            vals.append(part.val)
            part = part.next
        print(vals)

Line Notes

parts = [None] * kPreallocate result array for parts

parts[i] = currentAssign current node as head of ith part

size = part_size + (1 if remainder > 0 else 0)Calculate size of current part

if remainder > 0: remainder -= 1Decrement remainder after assigning extra node

for j in range(size - 1):Move pointer to last node of current part

current.next = NoneBreak link to separate current part

current = next_partMove to next part's head

return partsReturn array of part heads

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        int totalNodes = 0;
        ListNode current = head;
        while (current != null) {
            totalNodes++;
            current = current.next;
        }

        int partSize = totalNodes / k;
        int remainder = totalNodes % k;

        ListNode[] parts = new ListNode[k];
        current = head;

        for (int i = 0; i < k; i++) {
            parts[i] = current;
            int size = partSize + (remainder > 0 ? 1 : 0);
            if (remainder > 0) remainder--;

            for (int j = 0; j < size - 1; j++) {
                if (current != null) current = current.next;
            }

            if (current != null) {
                ListNode nextPart = current.next;
                current.next = null;
                current = nextPart;
            }
        }

        return parts;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        ListNode head = new ListNode(1);
        ListNode curr = head;
        for (int i = 2; i <= 10; i++) {
            curr.next = new ListNode(i);
            curr = curr.next;
        }
        ListNode[] parts = sol.splitListToParts(head, 3);
        for (ListNode part : parts) {
            ListNode temp = part;
            System.out.print("[");
            while (temp != null) {
                System.out.print(temp.val);
                temp = temp.next;
                if (temp != null) System.out.print(",");
            }
            System.out.println("]");
        }
    }
}

Line Notes

ListNode[] parts = new ListNode[k];Preallocate array for parts

parts[i] = current;Assign current node as head of ith part

int size = partSize + (remainder > 0 ? 1 : 0);Calculate size of current part

if (remainder > 0) remainder--;Decrement remainder after assigning extra node

for (int j = 0; j < size - 1; j++)Move pointer to last node of current part

current.next = null;Break link to separate current part

current = nextPart;Move to next part's head

return parts;Return array of part heads

#include <iostream>
#include <vector>
using namespace std;

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

class Solution {
public:
    vector<ListNode*> splitListToParts(ListNode* head, int k) {
        int totalNodes = 0;
        ListNode* current = head;
        while (current) {
            totalNodes++;
            current = current->next;
        }

        int partSize = totalNodes / k;
        int remainder = totalNodes % k;

        vector<ListNode*> parts(k, nullptr);
        current = head;

        for (int i = 0; i < k; i++) {
            parts[i] = current;
            int size = partSize + (remainder > 0 ? 1 : 0);
            if (remainder > 0) remainder--;

            for (int j = 0; j < size - 1; j++) {
                if (current) current = current->next;
            }

            if (current) {
                ListNode* nextPart = current->next;
                current->next = nullptr;
                current = nextPart;
            }
        }

        return parts;
    }
};

ListNode* createLinkedList(const vector<int>& vals) {
    ListNode dummy(0);
    ListNode* curr = &dummy;
    for (int v : vals) {
        curr->next = new ListNode(v);
        curr = curr->next;
    }
    return dummy.next;
}

void printParts(const vector<ListNode*>& parts) {
    for (auto part : parts) {
        cout << "[";
        ListNode* curr = part;
        while (curr) {
            cout << curr->val;
            curr = curr->next;
            if (curr) cout << ",";
        }
        cout << "]\n";
    }
}

int main() {
    Solution sol;
    ListNode* head = createLinkedList({1,2,3,4,5,6,7,8,9,10});
    int k = 3;
    vector<ListNode*> parts = sol.splitListToParts(head, k);
    printParts(parts);
    return 0;
}

Line Notes

vector<ListNode*> parts(k, nullptr);Preallocate vector for parts

parts[i] = current;Assign current node as head of ith part

int size = partSize + (remainder > 0 ? 1 : 0);Calculate size of current part

if (remainder > 0) remainder--;Decrement remainder after assigning extra node

for (int j = 0; j < size - 1; j++)Move pointer to last node of current part

current->next = nullptr;Break link to separate current part

current = nextPart;Move to next part's head

return parts;Return vector of part heads

function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

function splitListToParts(head, k) {
    let totalNodes = 0;
    let current = head;
    while (current !== null) {
        totalNodes++;
        current = current.next;
    }

    let partSize = Math.floor(totalNodes / k);
    let remainder = totalNodes % k;

    const parts = new Array(k).fill(null);
    current = head;

    for (let i = 0; i < k; i++) {
        parts[i] = current;
        let size = partSize + (remainder > 0 ? 1 : 0);
        if (remainder > 0) remainder--;

        for (let j = 0; j < size - 1; j++) {
            if (current !== null) current = current.next;
        }

        if (current !== null) {
            let nextPart = current.next;
            current.next = null;
            current = nextPart;
        }
    }

    return parts;
}

function createLinkedList(arr) {
    let dummy = new ListNode(0);
    let curr = dummy;
    for (let val of arr) {
        curr.next = new ListNode(val);
        curr = curr.next;
    }
    return dummy.next;
}

const head = createLinkedList([1,2,3,4,5,6,7,8,9,10]);
const k = 3;
const parts = splitListToParts(head, k);
for (const part of parts) {
    let vals = [];
    let curr = part;
    while (curr !== null) {
        vals.push(curr.val);
        curr = curr.next;
    }
    console.log(vals);
}

Line Notes

const parts = new Array(k).fill(null);Preallocate array for parts

parts[i] = current;Assign current node as head of ith part

let size = partSize + (remainder > 0 ? 1 : 0);Calculate size of current part

if (remainder > 0) remainder--;Decrement remainder after assigning extra node

for (let j = 0; j < size - 1; j++)Move pointer to last node of current part

current.next = null;Break link to separate current part

current = nextPart;Move to next part's head

return parts;Return array of part heads

⏱

Complexity

TimeO(n + k)

SpaceO(k) for output array

Counting nodes and splitting is done in linear time with respect to list size, plus output array allocation.

💡 This approach is clean and efficient, suitable for large inputs and interviews.

Interview Verdict: Accepted

This is the preferred approach to implement in interviews due to clarity and efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, implement the optimized one-pass approach with preallocation and inline splitting for clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Multiple Passes)	O(n + k)	O(k)	No	Yes	Mention only - good to explain problem understanding
2. One-Pass Split Using Precomputed Sizes	O(n + k)	O(k)	No	Yes	Good to code if asked for optimization
3. Optimized One-Pass with Preallocation	O(n + k)	O(k)	No	Yes	Best approach to implement in interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach, and progressively optimize. Practice coding and testing edge cases.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach by counting nodes and splitting in multiple passes.Step 3: Optimize by calculating sizes first and splitting in one pass.Step 4: Implement the cleanest solution with preallocation and inline splitting.Step 5: Test with edge cases and explain time and space complexity.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 7min. Total ~25min

What the Interviewer Tests

The interviewer tests your understanding of linked list traversal, pointer manipulation, handling edge cases like empty parts, and your ability to optimize from brute force to efficient code.

Common Follow-ups

• What if the list is extremely large? → Use O(n) time and O(k) space approach as shown.
• Can you do it without counting nodes first? → Not easily, because sizes depend on total length.

💡 These follow-ups test your understanding of constraints and whether you can adapt your solution to different scenarios.

🔍

Pattern Recognition

When to Use

1) You need to split or partition a linked list into parts; 2) The parts must be as equal as possible; 3) The problem involves distributing remainder nodes; 4) You must return multiple linked list heads.

Signature Phrases

'split linked list into k parts''length of each part as equal as possible''no two parts differ in size by more than one'

NOT This Pattern When

Problems that require rearranging nodes without splitting into parts, or problems that split arrays instead of linked lists.

Similar Problems

Split Array into Consecutive Subsequences - similar partitioning logicPartition List - splitting linked list based on valueSplit Linked List to Parts (variant) - same problem with slight constraints

Practice

1. Consider the following code snippet implementing the optimal approach to copy a list with random pointers. Given the input list: 1 -> 2 -> 3, where node 1's random points to node 3, node 2's random points to node 1, and node 3's random is null, what is the value of copy_curr.random.val after the last iteration of the separation step (Step 3)?

easy

A. 1

B. 3

C. None (random pointer is null)

D. 2

Solution

1. Step 1: Trace Step 1 (Interleaving nodes)

   Original list: 1->2->3. After interleaving: 1->1'->2->2'->3->3'.

2. Step 2: Trace Step 2 (Assign random pointers)

   Node 1's random points to 3, so 1'.random = 3'. Node 2's random points to 1, so 2'.random = 1'. Node 3's random is null, so 3'.random = null.

3. Step 3: Trace Step 3 (Separate lists)

   After separation, copy_curr starts at 1'. After last iteration, copy_curr is at 3'. Its random pointer is null, so copy_curr.random.val does not exist.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   copy_curr.random is null after last iteration [OK]

Hint: Random pointers point to copied nodes via original's next [OK]

Common Mistakes:

• Confusing original and copied nodes during separation
• Off-by-one error in advancing copy_curr
• Assuming random pointers remain unchanged

2. Given the following code for odd-even linked list rearrangement, what is the output list after running the function on the input list [1, 2, 3, 4]?

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

def oddEvenList(head):
    if not head or not head.next:
        return head
    odd = head
    even = head.next
    even_head = even
    while even and even.next:
        odd.next = even.next
        odd = odd.next
        even.next = odd.next
        even = even.next
    odd.next = even_head
    return head

# Input list: 1 -> 2 -> 3 -> 4
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
new_head = oddEvenList(head)
curr = new_head
res = []
while curr:
    res.append(curr.val)
    curr = curr.next
print(res)

easy

A. [1, 2, 3, 4]

B. [1, 3, 2, 4]

C. [2, 4, 1, 3]

D. [1, 3, 4, 2]

Solution

1. Step 1: Trace first iteration of while loop

   odd=1, even=2, even.next=3; odd.next=3, odd moves to 3; even.next=4, even moves to 4.

2. Step 2: Loop ends as even.next is null; link odd.next to even_head (2)

   Final list order: 1 -> 3 -> 2 -> 4.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Output matches expected odd-even rearrangement for input [1,2,3,4] [OK]

Hint: Odd nodes first, then even nodes in original order [OK]

Common Mistakes:

• Confusing node values with indices
• Off-by-one errors in pointer updates

3. What is the space complexity of the optimal approach that copies a linked list with random pointers by weaving copied nodes into the original list and then separating them?

medium

A. O(n) due to storing copied nodes in a hash map

B. O(n) because each node's random pointer requires extra space

C. O(n) due to recursion stack in the copying process

D. O(1) because no extra data structures are used besides new nodes

Solution

1. Step 1: Identify auxiliary space usage

   The optimal approach weaves copied nodes directly into the original list without using extra hash maps or recursion.

2. Step 2: Confirm space complexity

   Only new nodes are created, which is required output space, so auxiliary space is O(1).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   No extra data structures or recursion stack used [OK]

Hint: Weaving nodes avoids extra mapping space [OK]

Common Mistakes:

• Confusing output space with auxiliary space
• Assuming recursion is used and adds stack space
• Thinking random pointers require extra space

4. What is the space complexity of the recursive reorder list approach that uses a helper function with recursion to reorder the list in place?

medium

A. O(n) -- recursion stack uses space proportional to list length

B. O(1) -- only constant extra pointers used

C. O(log n) -- recursion depth is halved each call

D. O(n^2) -- due to repeated pointer updates in recursion

Solution

1. Step 1: Identify recursion depth

   The helper function recurses once per node, so recursion depth is n.

2. Step 2: Calculate space usage

   Each recursive call adds stack frame, so total space is O(n), not constant or logarithmic.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Recursion stack proportional to list length [OK]

Hint: Recursion depth equals list length -> O(n) space [OK]

Common Mistakes:

• Assuming constant space due to in-place changes
• Confusing recursion depth with log n
• Overestimating to quadratic space

5. What is the time complexity of the optimal iterative approach that reverses a linked list in groups of k nodes, and why?

medium

A. O(nk), because each group reversal takes O(k) and there are n/k groups.

B. O(n), because each node is visited and reversed exactly once.

C. O(n log k), because reversing each group involves log k steps due to pointer updates.

D. O(n + k), because the algorithm traverses the list plus reverses k nodes.

Solution

1. Step 1: Analyze group reversal cost

   Each group of k nodes is reversed in O(k) time.

2. Step 2: Count total groups and total nodes processed

   There are approximately n/k groups, so total time is O(k * n/k) = O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Each node is processed once during reversal [OK]

Hint: Total nodes processed once -> O(n) time [OK]

Common Mistakes:

• Multiplying n by k incorrectly
• Assuming log k factor in reversal
• Ignoring that groups partition the list