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.