Bird
Raised Fist0
Interview Prepfast-slow-pointersmediumGoogleAmazon

Split Linked List in Parts

Choose your preparation mode4 modes available
🎯
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.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute Force (Multiple Passes)O(n + k)O(k)NoYesMention only - good to explain problem understanding
2. One-Pass Split Using Precomputed SizesO(n + k)O(k)NoYesGood to code if asked for optimization
3. Optimized One-Pass with PreallocationO(n + k)O(k)NoYesBest 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/5)
1. You are given a doubly linked list where some nodes have a child pointer to another doubly linked list. The child list may also have one or more children of its own, and so on, creating a multilevel data structure. Which approach guarantees an optimal solution to flatten this multilevel doubly linked list into a single-level doubly linked list preserving the original order?
easy
A. Use a recursive depth-first traversal that returns the tail of each flattened child list and connects it back to the parent list.
B. Use a breadth-first traversal with a queue to process nodes level by level, appending child lists at the end of the current level.
C. Iteratively traverse the list, and whenever a node has a child, find the tail of the child list and splice it between the current node and its next node, updating all pointers in-place without extra space.
D. Apply a greedy approach that always flattens the child list with the largest number of nodes first to minimize pointer updates.

Solution

  1. Step 1: Understand the problem structure

    The problem requires flattening a multilevel doubly linked list into a single-level list while preserving the order of nodes as they appear in depth-first traversal.
  2. Step 2: Evaluate approaches

    Recursive DFS (A) works but uses extra stack space. The in-place iterative approach (B) efficiently flattens by splicing child lists without extra space. BFS (C) changes order and is not optimal. Greedy (D) does not guarantee correct order.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    In-place iterative flattening preserves order and uses O(1) extra space [OK]
Hint: In-place iterative splicing preserves order and uses no extra space [OK]
Common Mistakes:
  • Confusing BFS with DFS order
  • Assuming recursion is always optimal
  • Thinking greedy approach reduces pointer updates
2. The following code attempts to implement the two stacks browser history. Identify the line containing the subtle bug that causes forward navigation to return outdated pages after visiting a new URL.
class BrowserHistory:
    def __init__(self, homepage: str):
        self.back_stack = [homepage]
        self.forward_stack = []

    def visit(self, url: str) -> None:
        self.back_stack.append(url)
        # Missing forward_stack.clear() here

    def back(self, steps: int) -> str:
        while steps > 0 and len(self.back_stack) > 1:
            self.forward_stack.append(self.back_stack.pop())
            steps -= 1
        return self.back_stack[-1]

    def forward(self, steps: int) -> str:
        while steps > 0 and self.forward_stack:
            self.back_stack.append(self.forward_stack.pop())
            steps -= 1
        return self.back_stack[-1]
medium
A. Line where back_stack.append(url) is called in visit
B. Line where forward_stack.clear() should be called but is missing in visit
C. Line where back_stack.pop() is called in back method
D. Line where forward_stack.pop() is called in forward method

Solution

  1. Step 1: Identify visit method behavior

    Visit appends new URL but does not clear forward_stack, so forward history remains outdated.
  2. Step 2: Understand impact on forward navigation

    Without clearing forward_stack, forward() returns stale pages that should have been discarded.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Clearing forward_stack on visit is essential to maintain correct forward history [OK]
Hint: Visit must clear forward history to avoid stale pages [OK]
Common Mistakes:
  • Forgetting to clear forward stack on visit
  • Incorrectly popping from back stack
  • Mismanaging stack boundaries
3. Examine the following buggy code snippet from an optimal linked list implementation. Which line contains the subtle bug that can cause the tail pointer to point to a deleted node after a deletion at the tail?
medium
A. Line 8: self.tail = prev
B. Line 6: prev.next = prev.next.next
C. Line 3: if index < 0 or index >= self.size:
D. Line 7: if index == self.size - 1:

Solution

  1. Step 1: Understand tail update condition

    The tail pointer should update when deleting the last node, which is at index size-1 before deletion.
  2. Step 2: Identify bug

    At line 8, the tail pointer is set to prev, but prev may not be the correct new tail if the deleted node was the last node. The tail pointer should be updated after size decrement and possibly set to the correct node.
  3. Step 3: Correct fix

    Update tail pointer after size decrement and ensure it points to the last node in the list.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Tail pointer update must correctly reflect the new last node after deletion [OK]
Hint: Tail pointer update must be done carefully after deletion [OK]
Common Mistakes:
  • Updating tail before size decrement
  • Not updating tail on last node deletion
  • Incorrect traversal to prev node
4. Consider the following buggy code for partitioning a linked list around value x. Which line contains the subtle bug that can cause an infinite loop or incorrect list structure?
medium
A. Line where less_tail is updated to current
B. Line where current.next is set to less_tail.next
C. Missing line to set the last node's next to None
D. Line where prev.next is updated to current.next

Solution

  1. Step 1: Identify the bug from known mistakes

    The code does not explicitly terminate the greater or equal partition's last node with None, which can cause cycles or incorrect traversal.
  2. Step 2: Confirm no line sets last node's next to None

    All pointer updates are correct, but missing termination leads to infinite loops or corrupted list.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Proper termination of the list is essential to avoid cycles [OK]
Hint: Always terminate the last node's next with None [OK]
Common Mistakes:
  • Forgetting to set last node's next to None
  • Incorrect pointer updates causing lost nodes
  • Misplacing less_tail pointer updates
5. Consider the following buggy code snippet for reversing nodes in k-groups. Which line contains the subtle bug that can cause incorrect output when the list length is not a multiple of k?
medium
A. Line missing the check 'if count < k: break' after counting nodes
B. Line with 'group_next = kth.next' assignment
C. Line with 'while kth.next and count < k:' loop
D. Line with 'tmp.next = group_next' pointer update

Solution

  1. Step 1: Identify missing boundary check

    The code does not check if the remaining nodes are fewer than k before reversal.
  2. Step 2: Consequence of missing check

    Without 'if count < k: break', partial groups get reversed incorrectly, breaking problem constraints.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Missing break causes partial group reversal [OK]
Hint: Always check group size before reversal [OK]
Common Mistakes:
  • Forgetting to break on partial group
  • Misplacing pointer updates
  • Assuming kth always valid
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard