Split Linked List in Parts

▶

Steps

setup

Initialize total_nodes and current pointer

Set total_nodes to 0 and current pointer to head of the list to start counting nodes.

💡 Counting nodes is essential to determine how to split the list evenly.

Line:

total_nodes = 0
current = head

💡 We start with no nodes counted and a pointer at the list head.

traverse

Count first node

Increment total_nodes to 1 because current points to the first node with value 1. Move current to next node.

💡 Each node visited increases the count to find total length.

Line:

total_nodes += 1
current = current.next

💡 We have counted one node and moved forward to continue counting.

traverse

Count second node

Increment total_nodes to 2 as current points to node with value 2. Move current to next node.

💡 Counting nodes one by one ensures accurate total length.

Line:

total_nodes += 1
current = current.next

💡 We have counted two nodes so far.

traverse

Count third node

Increment total_nodes to 3 as current points to node with value 3. Move current to next node which is null, ending count.

💡 Reaching null means we have counted all nodes.

Line:

total_nodes += 1
current = current.next

💡 Total nodes counted is 3.

setup

Calculate part size and remainder

Calculate base part size as total_nodes // k = 3 // 5 = 0 and remainder as total_nodes % k = 3 % 5 = 3.

💡 Base size and remainder determine how nodes are distributed among parts.

Line:

part_size = total_nodes // k
remainder = total_nodes % k

💡 Parts will have size 0 or 1 depending on remainder.

setup

Initialize parts array and reset current pointer

Create an array parts of size k with all None and reset current pointer to head to start splitting.

💡 Parts array will hold the head of each split part.

Line:

parts = [None] * k
current = head

💡 Ready to assign nodes to parts.

fill_row

Assign first part head and calculate size

Set parts[0] to current node (1). Calculate size as part_size + 1 because remainder > 0, so size = 1. Decrement remainder to 2.

💡 Parts with remainder get one extra node.

Line:

parts[i] = current
size = part_size + (1 if remainder > 0 else 0)
if remainder > 0:
    remainder -= 1

💡 First part will have one node.

traverse

Traverse to end of first part

Since size is 1, no inner loop traversal needed. Current points to node 1, which is the end of this part.

💡 For size 1, the part is just one node, no traversal inside part needed.

Line:

for j in range(size - 1):
    if current:
        current = current.next

💡 Current is at last node of part 0.

split

Break link to separate first part

Save next_part as current.next (node 2). Break link by setting current.next to None. Move current pointer to next_part (node 2).

💡 Breaking the link isolates the first part from the rest of the list.

Line:

if current:
    next_part = current.next
    current.next = None
    current = next_part

💡 First part is now a standalone list with one node.

fill_row

Assign second part head and calculate size

Set parts[1] to current node (2). Calculate size as part_size + 1 because remainder > 0, so size = 1. Decrement remainder to 1.

💡 Second part also gets one node due to remainder.

Line:

parts[i] = current
size = part_size + (1 if remainder > 0 else 0)
if remainder > 0:
    remainder -= 1

💡 Second part will have one node.

traverse

Traverse to end of second part

Since size is 1, no inner loop traversal needed. Current points to node 2, end of this part.

💡 No traversal needed for size 1 parts.

Line:

for j in range(size - 1):
    if current:
        current = current.next

💡 Current is at last node of part 1.

split

Break link to separate second part

Save next_part as current.next (node 3). Break link by setting current.next to None. Move current pointer to next_part (node 3).

💡 Breaking link isolates second part.

Line:

if current:
    next_part = current.next
    current.next = None
    current = next_part

💡 Second part is now isolated.

fill_row

Assign third part head and calculate size

Set parts[2] to current node (3). Calculate size as part_size + 1 because remainder > 0, so size = 1. Decrement remainder to 0.

💡 Third part also gets one node due to remainder.

Line:

parts[i] = current
size = part_size + (1 if remainder > 0 else 0)
if remainder > 0:
    remainder -= 1

💡 Third part will have one node.

traverse

Traverse to end of third part

Since size is 1, no inner loop traversal needed. Current points to node 3, end of this part.

💡 No traversal needed for size 1 parts.

Line:

for j in range(size - 1):
    if current:
        current = current.next

💡 Current is at last node of part 2.

split

Break link to separate third part

Save next_part as current.next (null). Break link by setting current.next to None (already None). Move current pointer to next_part (null).

💡 Breaking link isolates third part; current becomes null indicating no more nodes.

Line:

if current:
    next_part = current.next
    current.next = None
    current = next_part

💡 Third part is isolated; no more nodes remain.

fill_row

Assign empty fourth part

Set parts[3] to current which is null, indicating an empty part.

💡 When no nodes remain, parts are empty (None).

Line:

parts[i] = current

💡 Empty parts are represented by None.

fill_row

Assign empty fifth part

Set parts[4] to current which is null, indicating an empty part.

💡 Remaining parts with no nodes are empty.

Line:

parts[i] = current

💡 All parts are assigned, including empty ones.

reconstruct

Return parts array as result

Return the array parts containing heads of each split part, including empty parts represented by None.

💡 The final output is an array of linked list heads representing each part.

Line:

return parts

💡 The list is split into k parts as required.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def splitListToParts(head, k):
    total_nodes = 0  # STEP 1
    current = head  # STEP 1
    while current:  # STEP 2-4 loop
        total_nodes += 1  # STEP 2-4
        current = current.next  # STEP 2-4

    part_size = total_nodes // k  # STEP 5
    remainder = total_nodes % k  # STEP 5

    parts = [None] * k  # STEP 6
    current = head  # STEP 6

    for i in range(k):  # STEP 7-17 loop
        parts[i] = current  # STEP 7,10,13,16,17
        size = part_size + (1 if remainder > 0 else 0)  # STEP 7,10,13
        if remainder > 0:  # STEP 7,10,13
            remainder -= 1  # STEP 7,10,13

        for j in range(size - 1):  # STEP 8,11,14
            if current:
                current = current.next

        if current:  # STEP 9,12,15
            next_part = current.next
            current.next = None
            current = next_part

    return parts  # STEP 18

📊

Split Linked List in Parts - Watch the Algorithm Execute, Step by Step

Watching each pointer move and link break helps you understand how the list is divided evenly and why some parts may be empty.

advance

1

→

2

→

3

advance

1

→

2

→

3

Result: 1

advance

1

→

2

→

3

Result: 2

advance

1

→

2

→

3

Result: 3

advance

1

→

2

→

3

Result:

Part size:0

Remainder:3

advance

1

→

2

→

3

Result:

Parts:[null, null, null, null, null]

connect

1

→

2

→

3

Result:

Parts:[[1], null, null, null, null]

Remainder:2

advance

1

→

2

→

3

Result:

Parts:[[1], null, null, null, null]

detach

1

→

2

→

3

Result:

Parts:[[1], null, null, null, null]

connect

1

→

2

→

3

Result:

Parts:[[1], [2], null, null, null]

Remainder:1

advance

1

→

2

→

3

Result:

Parts:[[1], [2], null, null, null]

detach

1

→

2

→

3

Result:

Parts:[[1], [2], null, null, null]

connect

1

→

2

→

3

Result:

Parts:[[1], [2], [3], null, null]

Remainder:0

advance

1

→

2

→

3

Result:

Parts:[[1], [2], [3], null, null]

detach

1

→

2

→

3

Result:

Parts:[[1], [2], [3], null, null]

connect

1

→

2

→

3

Result:

Parts:[[1], [2], [3], null, null]

connect

1

→

2

→

3

Result:

Parts:[[1], [2], [3], null, null]

reconstruct

1

→

2

→

3

Result: [[1], [2], [3], null, null]

Key Takeaways

✓ The algorithm counts nodes first to determine exact part sizes and remainder for even distribution.

This counting step is crucial and often overlooked; without it, splitting evenly is impossible.

✓ Parts with remainder get one extra node, ensuring the first few parts are larger if nodes don't divide evenly.

Visualizing remainder distribution clarifies why some parts have one node and others are empty.

✓ Breaking links inline isolates parts without extra memory, showing efficient in-place list manipulation.

Seeing links broken step-by-step reveals how the list is physically split, which is hard to grasp from code alone.

Practice

1. What is the time and space complexity of the optimal single-pass two-pointer approach to find the middle node of a singly linked list with n nodes?

medium

A. Time: O(n), Space: O(1)

B. Time: O(n^2), Space: O(1)

C. Time: O(n), Space: O(n)

D. Time: O(log n), Space: O(1)

Solution

1. Step 1: Identify time complexity

   Fast pointer moves two steps per iteration, slow moves one; total iterations proportional to n -> O(n) time.

2. Step 2: Identify space complexity

   Only two pointers used, no extra data structures -> O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time and constant space for two-pointer traversal [OK]

Hint: Two pointers traverse list once, no extra storage [OK]

Common Mistakes:

• Confusing space with O(n) due to recursion
• Assuming nested loops cause O(n^2)
• Thinking fast pointer halves complexity to O(log n)

2. Consider the following code snippet for palindrome check. Which line contains a subtle bug that can cause incorrect results on odd-length lists?

medium

A. Line where second_half_start is assigned by reversing slow

B. Line where slow pointer is advanced in the while loop

C. Line where first_half_start and second_half_start values are compared

D. Line where fast pointer is advanced in the while loop

Solution

1. Step 1: Understand midpoint selection

   For odd-length lists, slow points to the middle node, which should be skipped before reversal.

2. Step 2: Identify bug in reversal start

   Reversing from slow includes the middle node, causing mismatch in comparison.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct approach skips middle node before reversal on odd-length lists [OK]

Hint: Check if middle node is excluded before reversing second half [OK]

Common Mistakes:

• Reversing from slow without skipping middle node
• Incorrect fast/slow pointer advancement
• Not handling odd-length lists separately

3. Suppose the problem is modified so that after deleting N nodes, the deleted nodes can be reinserted later in the list (i.e., nodes can be reused). Which of the following changes to the algorithm is necessary to correctly handle this variant?

hard

A. Use a recursive approach to backtrack and reinsert deleted nodes at correct positions.

B. Maintain a separate data structure to store deleted nodes and reinsert them after traversal.

C. Modify the iterative approach to skip M nodes, delete N nodes, and immediately reattach deleted nodes after the next M nodes.

D. No change needed; the original iterative approach already supports node reuse.

Solution

1. Step 1: Understand node reuse requirement

   Deleted nodes must be preserved and reinserted later, so they cannot be simply discarded by pointer reassignment.

2. Step 2: Evaluate algorithm changes

   The original approach loses references to deleted nodes. To reuse, store deleted nodes externally and reinsert after traversal or at correct positions.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Maintaining deleted nodes separately enables controlled reinsertion [OK]

Hint: Reusing nodes requires storing them, not discarding pointers [OK]

Common Mistakes:

• Assuming original approach supports reuse
• Trying to reattach nodes immediately without storage
• Using recursion unnecessarily

4. Suppose you want to find the middle node of a linked list, but the list is circular (the last node points back to the head). Which modification to the two-pointer approach correctly finds the middle node without infinite looping?

hard

A. Use the same two-pointer approach but add a visited set to detect cycles and stop when fast pointer revisits a node.

B. Use recursion to count nodes until the head is reached again, then find middle by index.

C. Convert the circular list to a linear list by breaking the cycle first, then apply the standard two-pointer approach.

D. Modify the loop to stop when fast or fast.next equals the head node, then return slow pointer.

Solution

1. Step 1: Understand circular list behavior

   In a circular list, fast pointer will loop infinitely unless we detect when it cycles back to head.

2. Step 2: Modify loop condition

   Stop when fast or fast.next equals head to avoid infinite loop; slow pointer will be at middle.

3. Step 3: Compare alternatives

   Visited set adds extra space; breaking cycle modifies input; recursion risks stack overflow.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Stopping at head detects cycle end without extra space [OK]

Hint: Detect cycle by checking if fast pointer returns to head [OK]

Common Mistakes:

• Using visited set wastes space
• Breaking cycle modifies input
• Recursion risks stack overflow

5. Suppose the problem is modified so that the linked list is circular (the last node points back to the head), and you need to remove the nth node from the end. Which approach correctly adapts to this scenario?

hard

A. First detect the cycle length by traversing until you return to the start, then remove the (length - n)th node using two pointers.

B. Use the same recursive backtracking approach without changes; it works for circular lists.

C. Break the cycle by setting the last node's next to None, then apply the standard two-pointer method.

D. Use a hash set to track visited nodes and remove the nth node from the end by counting backwards.

Solution

1. Step 1: Detect cycle length

   In a circular list, length is unknown; traverse until returning to start to find length.

2. Step 2: Use two pointers with known length

   Once length is known, use two pointers with gap n+1 to remove the target node safely.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Cycle length detection is necessary before removal [OK]

Hint: Must find cycle length before applying two-pointer removal [OK]

Common Mistakes:

• Applying recursion blindly on circular list causing infinite recursion
• Breaking cycle without restoring it, altering list structure
• Using hash sets unnecessarily increasing space