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. Given the following code, what is the output when calling nth_from_end(head, 3) where head is a linked list with values [5, 10, 15, 20]?

easy

A. 5

B. 15

C. 20

D. 10

Solution

1. Step 1: Trace stack contents after traversal

   Stack after pushing nodes: [5, 10, 15, 20]

2. Step 2: Pop n-1=2 times and then pop once more for value

   Pop 1: 20, Pop 2: 15, final pop returns 10 which is the 3rd from end

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   3rd from end in [5,10,15,20] is 10 [OK]

Hint: Stack top is last node; pop n times to get nth from end [OK]

Common Mistakes:

• Off-by-one popping
• Returning node instead of value
• Confusing index from front vs end

2. What is the time complexity of the optimized iterative approach for deleting N nodes after skipping M nodes in a singly linked list of length n? Assume M and N are constants.

medium

A. O(n)

B. O(n * (M + N))

C. O(n^2)

D. O(n + M + N)

Solution

1. Step 1: Identify loop behavior

   The algorithm traverses the list once, moving forward by skipping M nodes and deleting N nodes repeatedly.

2. Step 2: Analyze complexity

   Since M and N are constants, each iteration moves forward by at least M+N nodes, so total steps proportional to n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass traversal yields O(n) time complexity [OK]

Hint: Constant M, N means linear traversal dominates [OK]

Common Mistakes:

• Mistaking nested loops causing O(n*(M+N))
• Assuming quadratic due to inner loops
• Ignoring that M and N are constants

3. Suppose the problem is modified so that the array elements can be zero, representing no movement, and cycles of length 1 (self-loop) are now considered valid. Which modification to the original fast and slow pointer algorithm correctly handles this variant?

hard

A. Remove the check that breaks when slow == next_index(slow), allowing single-element loops to return True.

B. Add a condition to skip zeros in the outer loop and treat zero jumps as invalid for cycles.

C. Modify the direction check to allow zero as both positive and negative direction to include zero jumps.

D. Use a visited set to track indices and return True if any index is revisited, ignoring direction.

Solution

1. Step 1: Understand new problem constraints

   Zero jumps are allowed and single-element loops are valid cycles.

2. Step 2: Identify necessary algorithm change

   The original code breaks when slow == next_index(slow) to exclude single-element loops; removing this check allows detecting single-element cycles.

3. Step 3: Confirm direction and zero handling

   Zeros represent no movement; allowing them means direction check must still be consistent, but zero jumps can form valid cycles.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Removing single-element loop break correctly detects new valid cycles [OK]

Hint: Allow single-element loops by removing cycle length >1 check [OK]

Common Mistakes:

• Skipping zeros entirely
• Treating zero as both directions
• Ignoring direction consistency

4. Suppose the linked list nodes can be reused multiple times in cycles (i.e., cycles can overlap or nest). Which modification to the fast-slow pointer approach correctly detects and counts the length of the first cycle encountered?

hard

A. Use a hash set to track visited nodes to detect cycles and count length, since fast-slow pointers fail with overlapping cycles.

B. Modify the fast pointer to move three steps at a time to detect overlapping cycles faster.

C. Run the fast-slow pointer detection multiple times from different starting points to find all cycles.

D. Use fast-slow pointers as usual; overlapping cycles do not affect detection of the first cycle.

Solution

1. Step 1: Understand overlapping cycles scenario

   Overlapping or nested cycles mean fast-slow pointers may not reliably detect all cycles or count lengths correctly.

2. Step 2: Evaluate approaches for correctness

   Using a hash set tracks all visited nodes, ensuring detection of any cycle and accurate length counting despite overlaps.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Hash set approach handles complex cycle structures correctly [OK]

Hint: Fast-slow pointers detect only simple cycles reliably [OK]

Common Mistakes:

• Assuming fast-slow pointers handle overlapping cycles
• Increasing fast pointer speed breaks correctness
• Multiple runs of fast-slow pointers are inefficient and incomplete

5. If the linked list allows cycles (i.e., it may not terminate), which modification is necessary to safely find the nth node from the end?

hard

A. Use the two-pointer approach without changes; it will still work.

B. Use a stack to store nodes indefinitely until nth node is found.

C. First detect cycle using Floyd's cycle detection, then handle accordingly before finding nth node.

D. Increase n to a very large number to ensure traversal covers the cycle.

Solution

1. Step 1: Understand cycle impact

   If the list has a cycle, naive traversal will loop infinitely, breaking the algorithm.

2. Step 2: Detect and handle cycle

   Use Floyd's cycle detection to identify cycle presence and length, then adjust logic to avoid infinite loops.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Cycle detection is prerequisite for safe traversal [OK]

Hint: Detect cycle first to avoid infinite loops [OK]

Common Mistakes:

• Assuming list always terminates
• Using stack without cycle check
• Increasing n arbitrarily