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. Given the following recursive code to convert a binary number in a linked list to an integer, what is the final output when the linked list is 1 -> 0 -> 1?

easy

A. 3

B. 7

C. 6

D. 5

Solution

1. Step 1: Trace helper with node1 (val=1), acc=0

   acc = (0 << 1) | 1 = 1; recurse with node2

2. Step 2: Trace helper with node2 (val=0), acc=1

   acc = (1 << 1) | 0 = 2; recurse with node3

3. Step 3: Trace helper with node3 (val=1), acc=2

   acc = (2 << 1) | 1 = 5; recurse with None

4. Step 4: Trace helper with None, acc=5

   Return acc=5

5. Final Answer:

   Option D -> Option D

6. Quick Check:

   Binary 101 equals decimal 5 [OK]

Hint: Shift and OR accumulate bits from left to right [OK]

Common Mistakes:

• Off-by-one errors in shifting
• Confusing bitwise OR with addition
• Returning intermediate instead of final accumulated value

2. You are given a singly linked list where each node contains an additional pointer that can point to any node in the list or null. The task is to create a deep copy of this list, preserving both the next and random pointer structure. Which approach guarantees an optimal solution with O(n) time and O(1) extra space?

easy

A. Interleave copied nodes within the original list, assign random pointers using the interleaved structure, then separate the lists.

B. Use a hash map to store original-to-copy node mappings and create the copy in two passes.

C. Use a recursive function with memoization to copy nodes and their random pointers.

D. Traverse the list multiple times, copying nodes and random pointers separately without extra data structures.

Solution

1. Step 1: Understand the problem constraints

   The problem requires copying a complex linked list with random pointers efficiently.

2. Step 2: Identify the optimal approach

   Interleaving copied nodes within the original list allows assigning random pointers without extra space, then separating the lists restores the original and creates the copy.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Interleaving nodes achieves O(n) time and O(1) space [OK]

Hint: Interleaving nodes avoids extra space for mapping [OK]

Common Mistakes:

• Assuming recursion is always optimal
• Using extra hash maps increases space complexity
• Trying multiple traversals without mapping fails random pointer assignment

3. Given the following code for partitioning a linked list around value x = 3, and the input list: 1 -> 4 -> 2 -> 5, what is the final reordered list returned by the function?

easy

A. 1 -> 4 -> 2 -> 5

B. 1 -> 2 -> 4 -> 5

C. 2 -> 1 -> 4 -> 5

D. 4 -> 1 -> 2 -> 5

Solution

1. Step 1: Trace initial pointers with input 1 -> 4 -> 2 -> 5 and x=3

   Start with dummy -> 1 -> 4 -> 2 -> 5, less_tail and prev at dummy, current at 1.

2. Step 2: Process nodes

   Node 1 < 3, less_tail.next == current, move less_tail and prev forward. Node 4 >= 3, move prev and current forward. Node 2 < 3, less_tail.next != current, so remove 2 and insert after less_tail. Final list: 1 -> 2 -> 4 -> 5.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Nodes less than 3 appear first in original order, then others [OK]

Hint: Track less_tail and prev carefully to avoid skipping nodes [OK]

Common Mistakes:

• Swapping values instead of nodes
• Incorrect pointer updates causing lost nodes
• Assuming order changes within partitions

4. Consider the following Python code implementing the recursive reorder list approach. Given the input list 1->2->3, what is the printed output after calling reorderList(n1)?

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

def reorderList(head):
    def helper(front, back):
        if not back:
            return True
        if not helper(front, back.next):
            return False
        if front[0] == back or front[0].next == back:
            back.next = None
            return False
        tmp = front[0].next
        front[0].next = back
        back.next = tmp
        front[0] = tmp
        return True
    helper([head], head)

n3 = ListNode(3)
n2 = ListNode(2, n3)
n1 = ListNode(1, n2)
reorderList(n1)
curr = n1
while curr:
    print(curr.val, end=' ')
    curr = curr.next

easy

A. 1 3

B. 1 2 3

C. 1 3 2

D. 3 2 1

Solution

1. Step 1: Trace helper calls with input 1->2->3

   Recursion reaches back=null, then unwinds, linking nodes alternately: 1->3->2.

2. Step 2: Verify final list traversal output

   Prints nodes in order: 1 3 2, confirming correct reorder.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches reorder pattern for 3 nodes [OK]

Hint: Small input trace confirms reorder sequence [OK]

Common Mistakes:

• Assuming no reorder happens
• Stopping recursion too early
• Misplacing next pointers

5. You are given a singly linked list and an integer k. The task is to reverse the nodes of the list k at a time and return the modified list. If the number of nodes is not a multiple of k, the remaining nodes at the end should remain as is. Which approach guarantees an optimal solution with O(n) time and O(1) space complexity?

easy

A. Use a recursive approach that reverses k nodes at a time and recurses on the rest, relying on call stack for reversal.

B. Apply a dynamic programming approach to store reversed sublists and combine them for the final result.

C. Iteratively traverse the list, reversing each group of k nodes using a helper function, and reconnect groups with pointer manipulation.

D. Use a greedy approach that reverses nodes whenever possible without checking group boundaries.

Solution

1. Step 1: Understand problem constraints

   The problem requires reversing nodes in groups of k, preserving the order of leftover nodes if fewer than k remain.

2. Step 2: Evaluate approaches

   Recursive approach (A) uses extra stack space and risks overflow; DP (B) is not applicable; greedy (D) fails on partial groups. Iterative with helper (C) reverses groups efficiently with O(1) space.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Iterative helper method is standard optimal solution [OK]

Hint: Iterative helper reversal is optimal for O(1) space [OK]

Common Mistakes:

• Confusing recursion with iterative approach
• Assuming DP applies to linked list reversal
• Ignoring partial group handling