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 a singly linked list and two integers M and N. The task is to traverse the list, skip M nodes, then delete the next N nodes, and repeat this process until the end of the list. Which algorithmic approach best guarantees an optimal O(n) time and O(1) space solution for this problem?

easy

A. Use a recursive approach that deletes nodes during the unwinding phase of recursion.

B. Use a brute force nested loop approach that for each node checks ahead to delete N nodes repeatedly.

C. Use an iterative two-pointer approach that skips M nodes and deletes N nodes in a single pass.

D. Use a dynamic programming approach to store states of nodes to decide deletion.

Solution

1. Step 1: Understand the problem constraints

   The problem requires skipping M nodes and deleting N nodes repeatedly until the list ends, which suggests a linear traversal.

2. Step 2: Evaluate approaches

   Recursive approaches add extra space due to call stack; brute force nested loops increase time complexity; dynamic programming is unnecessary as no overlapping subproblems exist. The iterative two-pointer approach efficiently traverses once, skipping and deleting nodes in O(n) time and O(1) space.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Iterative two-pointer approach matches optimal time and space complexity [OK]

Hint: Iterative two-pointer approach is linear and space efficient [OK]

Common Mistakes:

• Thinking recursion is optimal despite extra stack space
• Using nested loops causing O(n²) time
• Misapplying DP to a linear traversal problem

2. Consider the following Python code implementing the optimal Happy Number check using a known cycle set. What is the output when the input is 7?

def isHappy(n: int) -> bool:
    cycle_set = {4, 16, 37, 58, 89, 145, 42, 20}

    def get_next(number):
        total_sum = 0
        while number > 0:
            digit = number % 10
            total_sum += digit * digit
            number //= 10
        return total_sum

    while n != 1 and n not in cycle_set:
        n = get_next(n)
    return n == 1

print(isHappy(7))

easy

A. Runtime error due to infinite loop

B. null (function returns no value)

C. true

D. false

Solution

1. Step 1: Trace the sequence starting from 7

   7 -> 49 (4²+9²=16+81=97) -> 97 -> 130 -> 10 -> 1 Detailed steps: 7 -> 49 (4²+9²=16+81=97) 97 -> 130 (9²+7²=81+49=130) 130 -> 10 (1²+3²+0²=1+9+0=10) 10 -> 1 (1²+0²=1+0=1) So it reaches 1.

2. Step 2: Check if the code returns true for n=7

   The loop terminates when n == 1, so the function returns true.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sequence reaches 1 -> returns true [OK]

Hint: Trace sum-of-squares sequence carefully [OK]

Common Mistakes:

• Miscompute sum of squares leading to wrong cycle detection

3. Given the following code for checking if a linked list is a palindrome, what is the final return value when the input list is 1 -> 2 -> 1?

easy

A. Infinite loop

B. False

C. True

D. Raises an exception due to null pointer

Solution

1. Step 1: Trace fast and slow pointers

   For list 1 -> 2 -> 1, slow ends at node with value 2, fast reaches end.

2. Step 2: Reverse second half and compare

   Second half starting at 2 -> 1 is reversed to 1 -> 2. Compare nodes: 1==1, 2==2, all match, so return True.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Palindrome list returns True after correct reversal and comparison [OK]

Hint: Check pointer movement and reversed half comparison carefully [OK]

Common Mistakes:

• Misplacing slow pointer causing wrong half reversal
• Off-by-one error in comparison loop
• Forgetting to advance second_half_start pointer

4. The following code attempts to detect a cycle in a circular array using the fast-slow pointer approach. Identify the line containing the subtle bug that causes incorrect cycle detection.

medium

A. Line with 'return true' inside while loop returns prematurely

B. Line with 'if slow == fast:' missing cycle length check

C. Line with 'direction = nums[i] > 0' incorrectly sets direction

D. Line with 'nums[marker] = 0' incorrectly marks visited elements

Solution

1. Step 1: Identify cycle detection condition

   The code returns true immediately when slow == fast, but does not check if cycle length > 1.

2. Step 2: Understand why self-loop is invalid

   Cycle of length 1 (self-loop) is invalid; must check if slow != next_index(slow) before returning true.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing cycle length check causes false positives [OK]

Hint: Check cycle length > 1 to avoid self-loop false positives [OK]

Common Mistakes:

• Returning true on self-loop cycles
• Mixing directions
• Not marking visited nodes

5. Suppose the linked list can have multiple cycles due to node reuse (e.g., a node's next pointer can point to any previously visited node, creating multiple cycle entries). Which modification to Floyd's algorithm correctly detects the first cycle start node encountered from the head?

hard

A. Run Floyd's algorithm repeatedly after removing detected cycles until no cycle remains.

B. Use two pointers but move fast pointer three steps at a time to detect multiple cycles faster.

C. Modify Floyd's algorithm to reset the fast pointer to head after detection and continue until slow and fast meet again.

D. Use a hash set to track visited nodes and return the first repeated node encountered during traversal.

Solution

1. Step 1: Understand multiple cycles scenario

   Floyd's algorithm assumes a single cycle; multiple cycles break its assumptions and can cause incorrect detection.

2. Step 2: Use hash set to detect first repeated node

   Tracking visited nodes with a hash set detects the first node that appears twice, correctly identifying the earliest cycle entry.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Hash set approach works correctly with multiple cycles but uses extra space [OK]

Hint: Floyd's algorithm fails with multiple cycles; hash set detects first repeated node [OK]

Common Mistakes:

• Trying to adapt Floyd's algorithm without extra space
• Assuming multiple cycles can't exist
• Increasing fast pointer speed doesn't help