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. You are given an array of n + 1 integers where each integer is between 1 and n (inclusive). There is exactly one duplicate number but it could be repeated multiple times. Which approach guarantees finding the duplicate in O(n) time and O(1) space without modifying the input array?

easy

A. Sort the array and then scan for consecutive duplicates

B. Use two pointers moving at different speeds to detect a cycle in the array values

C. Use a hash set to track seen numbers and return the first duplicate

D. Use nested loops to compare every pair of elements

Solution

1. Step 1: Understand the problem constraints

   The array contains n+1 integers with values from 1 to n, guaranteeing at least one duplicate. The input cannot be modified and extra space must be O(1).

2. Step 2: Identify the approach that fits constraints

   Sorting modifies the array, hash sets use extra space, nested loops are O(n²). Floyd's cycle detection uses two pointers at different speeds to find a cycle in O(n) time and O(1) space without modifying the array.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two-pointer cycle detection fits all constraints [OK]

Hint: Cycle detection fits O(n) time and O(1) space [OK]

Common Mistakes:

• Assuming sorting is allowed despite input constraints
• Believing hash sets use constant space
• Thinking nested loops are efficient enough

2. Given the following Python code for reorderList and the input list 1->2->3->4, what is the value of the node pointed to by left after the first merge step in the recursion unwinding?

easy

A. Node with value 3

B. Node with value 2

C. Node with value 4

D. Node with value 1

Solution

1. Step 1: Trace recursion to the end

   Recursion reaches right = None, then unwinds from node 4 back to node 1.

2. Step 2: First merge step during unwinding

   At right=4, left=1, tmp=left.next=2; left.next=4; 4.next=2; left=2 after merge.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   After first merge, left points to node with value 2 [OK]

Hint: left moves forward after merging right node [OK]

Common Mistakes:

• Confusing left pointer update
• Off-by-one in recursion unwind
• Misreading next pointer assignments

3. Examine the following code snippet intended to detect the start of a cycle in a linked list. Identify the line containing the subtle bug that can cause a runtime error or infinite loop.

medium

A. Line 5: fast = fast.next.next

B. Line 3: while fast:

C. Line 7: if slow == fast:

D. Line 11: while ptr1 != ptr2:

Solution

1. Step 1: Check loop condition safety

   The loop condition only checks if fast is not None, but fast.next may be None, so fast.next.next can cause an exception.

2. Step 2: Identify fix

   The loop condition should check both fast and fast.next to avoid null pointer exceptions.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Accessing fast.next.next without checking fast.next causes runtime error [OK]

Hint: Always check fast and fast.next before accessing fast.next.next [OK]

Common Mistakes:

• Missing fast.next check
• Returning meeting point as cycle start
• Infinite loop due to wrong loop condition

4. What is the time complexity of the optimized fast-slow pointer algorithm for detecting a cycle and counting its length in a linked list of n nodes?

medium

A. O(n²) because the inner loop counts cycle length after detection

B. O(n) because fast and slow pointers traverse nodes at most twice

C. O(n log n) due to repeated pointer jumps

D. O(n) but with O(n) auxiliary space for visited nodes

Solution

1. Step 1: Analyze fast and slow pointer traversal

   Fast pointer moves twice as fast as slow, so they meet within O(n) steps.

2. Step 2: Count cycle length with a single traversal

   After detection, counting cycle length requires traversing the cycle once, which is O(k) ≤ O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Overall time is linear in number of nodes [OK]

Hint: Fast-slow pointers meet in O(n), counting cycle is O(k) ≤ O(n) [OK]

Common Mistakes:

• Assuming counting cycle length is O(n²)
• Confusing space complexity with time
• Thinking recursion or extra data structures are used

5. If the linked list nodes can be reused multiple times (i.e., the list is cyclic or can be traversed repeatedly), which modification is necessary to the optimal palindrome check algorithm?

hard

A. No modification needed; the current algorithm works as is.

B. Use a stack to store first half values instead of reversing to avoid modifying the list.

C. Convert the list to an array to handle multiple traversals safely.

D. Restore the reversed second half to original order after comparison to preserve list structure.

Solution

1. Step 1: Understand reuse implications

   If nodes are reused or list is cyclic, modifying it breaks future traversals.

2. Step 2: Restore list after palindrome check

   Reversing second half in-place must be undone to preserve original list structure.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Restoring reversed half ensures list integrity for reuse [OK]

Hint: Always restore list after in-place reversal if list is reused [OK]

Common Mistakes:

• Ignoring list restoration causing side effects
• Switching to stack approach unnecessarily increasing space
• Assuming array conversion is always better