Bird
Raised Fist0
Interview Prepfast-slow-pointersmediumGoogleAmazon

Split Linked List in Parts

Choose your preparation mode4 modes available
</>
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
}
0/10
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
t1_01basic
Input{"head":[1,2,3],"k":5}
Expected[[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.

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]]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

k=1 means entire list is 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}
⏱ 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.

Practice

(1/5)
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. Consider the following Python code implementing browser history with two stacks. After executing the sequence of operations below, what is the output of the last back call?
browserHistory = BrowserHistory("leetcode.com")
browserHistory.visit("google.com")
browserHistory.visit("facebook.com")
browserHistory.visit("youtube.com")
print(browserHistory.back(1))
print(browserHistory.back(1))
print(browserHistory.forward(1))
easy
A. "youtube.com"
B. "google.com"
C. "facebook.com"
D. "leetcode.com"

Solution

  1. Step 1: Trace back(1) after visiting youtube.com

    back_stack = ["leetcode.com", "google.com", "facebook.com", "youtube.com"] Pop "youtube.com" to forward_stack, back_stack top is "facebook.com".
  2. Step 2: Trace back(1) again and forward(1)

    Second back(1): pop "facebook.com" to forward_stack, top is "google.com". Forward(1): pop "facebook.com" from forward_stack back to back_stack, top is "facebook.com".
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Last forward returns "facebook.com" as expected [OK]
Hint: Back and forward operations move URLs between stacks correctly [OK]
Common Mistakes:
  • Off-by-one errors in popping stacks
  • Confusing forward and back stacks
  • Returning wrong top element after operations
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 optimal approach that copies a linked list with random pointers by weaving copied nodes into the original list and then separating them?
medium
A. O(n) due to storing copied nodes in a hash map
B. O(n) because each node's random pointer requires extra space
C. O(n) due to recursion stack in the copying process
D. O(1) because no extra data structures are used besides new nodes

Solution

  1. Step 1: Identify auxiliary space usage

    The optimal approach weaves copied nodes directly into the original list without using extra hash maps or recursion.
  2. Step 2: Confirm space complexity

    Only new nodes are created, which is required output space, so auxiliary space is O(1).
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    No extra data structures or recursion stack used [OK]
Hint: Weaving nodes avoids extra mapping space [OK]
Common Mistakes:
  • Confusing output space with auxiliary space
  • Assuming recursion is used and adds stack space
  • Thinking random pointers require extra space
5. Identify the bug in the following code snippet implementing the odd-even linked list rearrangement:
def oddEvenList(head):
    if not head or not head.next:
        return head
    odd = head
    even = head.next
    even_head = even
    while even and even.next:
        odd.next = even.next
        odd = odd.next
        even.next = odd.next
        even = even.next
    # Missing termination of even list
    odd.next = even_head
    return head
What is the consequence of the missing line and how to fix it?
medium
A. The function does not handle empty lists; fix by adding a check for head == None at the start
B. The odd pointer is not updated correctly inside the loop; fix by moving 'odd = odd.next' after even pointer updates
C. The even_head pointer is lost; fix by initializing even_head after the loop instead of before
D. The even list is not terminated with null, causing a cycle; fix by adding 'if even: even.next = None' before linking odd.next

Solution

  1. Step 1: Understand pointer termination

    Without setting even.next = None, the even list may still point to old nodes, causing cycles or infinite loops.
  2. Step 2: Fix by terminating even list

    Adding 'if even: even.next = None' before linking odd.next ensures even list ends properly.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Proper termination prevents cycles and infinite traversal [OK]
Hint: Always terminate the last node's next with None to avoid cycles [OK]
Common Mistakes:
  • Forgetting to terminate even list causing infinite loops
  • Misplacing pointer updates causing node skips
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