Split Linked List in Parts

📋

Split Linked List in Parts

Edge cases:

</>

IDE

def splitListToParts(head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:public ListNode[] splitListToParts(ListNode head, int k)vector<ListNode*> splitListToParts(ListNode* head, int k)function splitListToParts(head, k)

def splitListToParts(head, k):
    # Write your solution here
    pass

class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        // Write your solution here
        return new ListNode[k];
    }
}

#include <vector>
using namespace std;

vector<ListNode*> splitListToParts(ListNode* head, int k) {
    // Write your solution here
    return vector<ListNode*>(k, nullptr);
}

function splitListToParts(head, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [[1,2],[3,4,5]]Greedy approach ignoring remainder distribution; parts differ by more than one node.✅ Distribute remainder nodes to first parts only: part_size + 1 for first remainder parts, part_size for others.

Wrong: [[1,2],[3,4],[5]]Off-by-one error in splitting; cutting list too early or late causing incorrect part sizes.✅ Move current pointer size-1 times before cutting and setting next to null.

Wrong: [[1],[2],[3],[4],[5]]Incorrect handling when k=1; splitting unnecessarily into multiple parts.✅ Return entire list as single part when k=1 without splitting.

Wrong: [[1],[2],[3],[],[]]Failed to return empty parts as empty lists or null; returned null or missing parts.✅ Always return k parts; empty parts as empty lists or null nodes.

Wrong: [[],[],[]]Failed to handle single node with k>1; returned all empty parts.✅ Assign one node to first part, rest empty.

✓

Test Cases

Focus on handling empty and minimal input cases correctly.

Watch out for subtle off-by-one and remainder distribution bugs.

Optimize your solution to run efficiently on large inputs.

t1_01basic

Input{"head":[1,2,3],"k":5}

Expected[[1],[2],[3],[],[]]

⏱ Performance - must finish in 2000ms

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

💡 Think about dividing the total nodes by k to get base part size.

💡 Calculate remainder nodes to distribute one extra node to first parts.

💡 Assign part_size + 1 nodes to first remainder parts, then part_size nodes to the rest.

Why it failed: Output incorrect: likely failed to handle remainder distribution or empty parts when k > list length. Fix by distributing remainder nodes to first parts and returning empty parts as null.

✓ Correctly splits list into k parts with proper size distribution.

t1_02basic

Input{"head":[1,2,3,4,5,6,7,8,9,10],"k":3}

Expected[[1,2,3,4],[5,6,7],[8,9,10]]

⏱ Performance - must finish in 2000ms

10 nodes split into 3 parts: first part has 4 nodes (one extra), next two parts have 3 nodes each.

💡 Divide total nodes by k to get base size and remainder.

💡 Distribute remainder nodes to first parts to balance sizes.

💡 Ensure parts differ in size by at most one.

Why it failed: Incorrect part sizes: likely ignored remainder or distributed nodes unevenly. Fix by adding one extra node to first remainder parts.

✓ Correctly balances parts sizes with remainder distribution.

t2_01edge

Input{"head":[],"k":3}

Expected[[],[],[]]

⏱ Performance - must finish in 2000ms

Empty list with k=3 results in all parts empty.

💡 Consider the case when the list is empty (head is null).

💡 All parts should be empty lists since no nodes exist.

💡 Return k empty parts regardless of list length.

Why it failed: Failed to handle empty list input; returned non-empty parts or null. Fix by returning k empty parts when head is null.

✓ Correctly returns k empty parts for empty list.

t2_02edge

Input{"head":[10],"k":3}

Expected[[10],[],[]]

⏱ Performance - must finish in 2000ms

Single node list with k=3: first part has one node, rest are empty.

💡 When list length < k, some parts will be empty.

💡 Assign one node to first part, then empty parts for remaining.

💡 Ensure no parts have more than one node if list length is 1.

Why it failed: Incorrectly assigned nodes or failed to create empty parts. Fix by assigning one node to first part and empty lists to others.

✓ Correctly handles single node with multiple parts.

t2_03edge

Input{"head":[1,2,3,4],"k":4}

Expected[[1],[2],[3],[4]]

⏱ Performance - must finish in 2000ms

k equals list length: each part has exactly one node.

💡 When k equals list length, each part should have exactly one node.

💡 No remainder to distribute since division is exact.

💡 Return each node as a separate part.

Why it failed: Failed to split into single-node parts; possibly merged nodes. Fix by assigning exactly one node per part when k == list length.

✓ Correctly splits list into single-node parts.

t2_04edge

Input{"head":[1],"k":1}

Expected[[1]]

⏱ Performance - must finish in 2000ms

Single node list with k=1 returns the entire list as one part.

💡 When k=1, return the entire list as a single part.

💡 No splitting or remainder distribution needed.

💡 Return array with one element: the head.

Why it failed: Incorrectly split list when k=1; possibly splitting unnecessarily. Fix by returning list as single part when k=1.

✓ Correctly returns entire list as one part.

t3_01corner

Input{"head":[1,2,3,4,5],"k":2}

Expected[[1,2,3],[4,5]]

⏱ Performance - must finish in 2000ms

5 nodes split into 2 parts: first part has 3 nodes (one extra), second has 2 nodes.

💡 Beware of greedy approach that assigns equal sizes without remainder.

💡 Check remainder distribution to first parts only.

💡 Add one extra node to first remainder parts, not all parts.

Why it failed: Greedy mistake: assigned equal sizes ignoring remainder. Fix by distributing remainder nodes only to first parts.

✓ Correctly distributes remainder nodes to first parts.

t3_02corner

Input{"head":[1,2,3,4,5],"k":3}

Expected[[1,2],[3,4],[5]]

⏱ Performance - must finish in 2000ms

5 nodes split into 3 parts: first two parts have 2 nodes, last part has 1 node.

💡 Avoid off-by-one errors when moving current pointer.

💡 Ensure to cut the list after size nodes, not size-1.

💡 Carefully update current pointer and set next to null.

Why it failed: Off-by-one error in splitting: parts have incorrect sizes or links not cut properly. Fix by moving current pointer size-1 times and cutting after.

✓ Correctly splits and cuts list parts with proper sizes.

t3_03corner

Input{"head":[1,2,3,4,5],"k":1}

Expected[[1,2,3,4,5]]

⏱ Performance - must finish in 2000ms

k=1 means entire list is one part.

💡 When k=1, return the entire list as single part.

💡 No splitting or remainder distribution needed.

💡 Return array with one element: the head.

Why it failed: Incorrectly split list when k=1; possibly splitting unnecessarily. Fix by returning list as single part when k=1.

✓ Correctly returns entire list as one part.

t4_01performance

Input{"head":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100000],"k":50}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100000 nodes and k=50; solution must run in O(n + k) time within 2 seconds.

💡 Avoid multiple passes over the list; count nodes once.

💡 Calculate part sizes and remainder before splitting.

💡 Split list in one pass using precomputed sizes.

Why it failed: TLE due to O(n*k) or multiple passes over list. Fix by using single pass splitting with precomputed sizes.

✓ Efficient O(n + k) solution confirmed.

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. You need to implement a data structure that supports the following operations efficiently: get element by index, add element at head, add element at tail, add element at an arbitrary index, and delete element at an arbitrary index. Which approach best guarantees efficient average-case performance for all these operations?

easy

A. Use a dynamic array and resize it when needed to support all operations.

B. Use a balanced binary search tree keyed by index to support all operations in O(log n).

C. Use a singly linked list with sentinel head and tail pointers, maintaining the size for boundary checks.

D. Use a hash map to store index-to-node mappings for constant time access.

Solution

1. Step 1: Understand operation requirements

   The problem requires efficient get, add at head, add at tail, add at index, and delete at index operations.

2. Step 2: Evaluate approaches

   Dynamic arrays have O(n) add/delete at head or arbitrary index due to shifting. Singly linked lists have O(1) add at head/tail but O(n) get and add/delete at arbitrary index. Balanced BSTs keyed by index can support all operations in O(log n) time, providing efficient average-case performance. Hash maps do not maintain order and cannot efficiently support index-based operations.

3. Step 3: Choose best approach

   Balanced BST keyed by index offers O(log n) for all operations, which is more efficient on average than linked list or array for arbitrary index operations.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Balanced BST supports all required operations efficiently [OK]

Hint: Balanced BST keyed by index supports all operations in O(log n) [OK]

Common Mistakes:

• Assuming linked list provides efficient arbitrary index access
• Thinking arrays support O(1) insertions at head
• Assuming hash maps maintain order

3. You are given a singly linked list and a value x. The task is to reorder the list so that all nodes with values less than x come before nodes with values greater than or equal to x, while preserving the original relative order within each partition. Which approach guarantees an optimal solution with O(n) time and O(1) space complexity?

easy

A. Extract all node values into arrays, reorder them, then rebuild the list.

B. Use two pointers to build two separate linked lists for nodes less than and greater or equal to x, then concatenate them.

C. Sort the entire linked list using merge sort and then split at value x.

D. Traverse the list once, rearranging nodes in-place by adjusting pointers without extra lists.

Solution

1. Step 1: Understand the problem constraints

   The problem requires partitioning the list around value x while preserving relative order and achieving O(n) time and O(1) space.

2. Step 2: Evaluate approaches

   Approach A uses extra arrays, so space is O(n). Approach B uses extra lists, so space is O(n). Approach D sorts the list, which is O(n log n) time. Only approach C rearranges nodes in-place in one pass with constant space.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   In-place rearrangement achieves O(n) time and O(1) space [OK]

Hint: In-place pointer rearrangement is O(1) space [OK]

Common Mistakes:

• Assuming sorting is needed to partition
• Using extra arrays or lists increases space
• Believing two separate lists always use constant 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. Suppose the linked list nodes can be reused multiple times (i.e., the list is cyclic or nodes appear multiple times). Which modification to the reorder list algorithm is necessary to handle this scenario correctly?

hard

A. Use a hash set to track visited nodes and avoid infinite loops during reordering.

B. No modification needed; the recursive approach handles cycles naturally.

C. Convert the list to an array first to handle duplicates, then reorder using indices.

D. Break the list into halves without reversing the second half to prevent cycles.

Solution

1. Step 1: Understand node reuse implications

   Reusing nodes or cycles cause infinite loops if not detected during traversal.

2. Step 2: Modify algorithm to track visited nodes

   Using a hash set to track visited nodes prevents revisiting and infinite loops.

3. Step 3: Evaluate other options

   Recursive approach alone cannot detect cycles; array conversion adds overhead; skipping reversal breaks reorder logic.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Tracking visited nodes prevents infinite loops in cyclic lists [OK]

Hint: Cycle detection requires visited node tracking [OK]

Common Mistakes:

• Assuming no cycles exist
• Relying on recursion without cycle checks
• Ignoring node reuse effects