Reverse Linked List in Groups of K (Generalization)

▶

Steps

setup

Initialize dummy node and pointers

Create a dummy node pointing to the head of the list. Initialize group_prev to dummy to start processing from the list head.

💡 Dummy node simplifies edge cases by providing a stable node before the head.

Line:

dummy = ListNode(0)
dummy.next = head
group_prev = dummy

💡 Dummy node allows uniform handling of head reversal and simplifies pointer updates.

traverse

Find kth node for first group

Move kth pointer k=2 steps ahead from group_prev to identify the end of the first group to reverse.

💡 Identifying the group boundary is essential before reversal.

Line:

kth = group_prev
count = 0
while kth.next and count < k:
    kth = kth.next
    count += 1

💡 kth pointer marks the last node of the current group to reverse.

traverse

Identify group_next after kth

Set group_next pointer to the node after kth, marking the start of the next group or end of list.

💡 group_next helps reconnect the reversed group to the rest of the list.

Line:

group_next = kth.next

💡 group_next points to the node after the current group, preserving the rest of the list.

reverse_link

Start reversing first group

Call reverseBetween to reverse nodes from group_prev.next (node 1) up to group_next (node 3). Initialize prev and curr pointers for reversal.

💡 Reversing the group changes the direction of next pointers within the group.

Line:

prev = None
curr = start  # start = group_prev.next (node 1)

💡 prev and curr pointers are used to reverse links one by one.

reverse_link

Reverse link: node 1 points to null

Detach node 1 from node 2 by pointing node 1's next to prev (null). Move prev to node 1 and curr to node 2.

💡 This reverses the first link in the group, starting the reversal chain.

Line:

nxt = curr.next
curr.next = prev
prev = curr
curr = nxt

💡 Reversing links one by one flips the group order.

reverse_link

Reverse link: node 2 points to node 1

Detach node 2 from node 3 by pointing node 2's next to prev (node 1). Move prev to node 2 and curr to node 3 (group_next).

💡 Completes reversal of the first group of size k=2.

Line:

nxt = curr.next
curr.next = prev
prev = curr
curr = nxt

💡 Now the first group is reversed: node 2 -> node 1 -> null.

connect

Reconnect reversed group to main list

Connect group_prev.next to prev (new head of reversed group) and the old group's head (tmp) next to group_next to reconnect the list.

💡 Reconnecting ensures the reversed group is linked back to the rest of the list.

Line:

tmp = group_prev.next
group_prev.next = prev
tmp.next = group_next

💡 Pointers are updated to maintain list integrity after reversal.

advance

Move group_prev to end of reversed group

Update group_prev to tmp (old head of reversed group, now tail) to prepare for next group reversal.

💡 Moving group_prev sets the stage for processing the next group.

Line:

group_prev = tmp

💡 group_prev always points to the node before the next group to reverse.

traverse

Find kth node for second group

Move kth pointer k=2 steps ahead from group_prev to identify the end of the second group to reverse.

💡 Repeat group boundary identification for the next group.

Line:

kth = group_prev
count = 0
while kth.next and count < k:
    kth = kth.next
    count += 1

💡 kth pointer marks the last node of the second group to reverse.

traverse

Identify group_next after kth for second group

Set group_next pointer to the node after kth (node 5), marking the start of the next group or end of list.

💡 group_next preserves the rest of the list after the current group.

Line:

group_next = kth.next

💡 group_next points to node 5, the start of the next group or tail.

reverse_link

Start reversing second group

Call reverseBetween to reverse nodes from group_prev.next (node 3) up to group_next (node 5). Initialize prev and curr pointers for reversal.

💡 Reversing the second group changes the direction of next pointers within this group.

Line:

prev = None
curr = start  # start = group_prev.next (node 3)

💡 prev and curr pointers are used again to reverse links one by one.

reverse_link

Reverse link: node 3 points to null

Detach node 3 from node 4 by pointing node 3's next to prev (null). Move prev to node 3 and curr to node 4.

💡 This reverses the first link in the second group.

Line:

nxt = curr.next
curr.next = prev
prev = curr
curr = nxt

💡 Reversing links one by one flips the group order.

reverse_link

Reverse link: node 4 points to node 3

Detach node 4 from node 5 by pointing node 4's next to prev (node 3). Move prev to node 4 and curr to node 5 (group_next).

💡 Completes reversal of the second group of size k=2.

Line:

nxt = curr.next
curr.next = prev
prev = curr
curr = nxt

💡 Now the second group is reversed: node 4 -> node 3 -> null.

connect

Reconnect reversed second group to main list

Connect group_prev.next to prev (new head of reversed group) and the old group's head (tmp) next to group_next to reconnect the list.

💡 Reconnecting ensures the reversed group is linked back to the rest of the list.

Line:

tmp = group_prev.next
group_prev.next = prev
tmp.next = group_next

💡 Pointers are updated to maintain list integrity after reversal.

advance

Move group_prev to end of reversed second group

Update group_prev to tmp (old head of reversed group, now tail) to prepare for next group reversal.

💡 Moving group_prev sets the stage for processing the next group.

Line:

group_prev = tmp

💡 group_prev always points to the node before the next group to reverse.

traverse

Attempt to find kth node for third group

Try to move kth pointer k=2 steps ahead from group_prev, but only one node (5) is available.

💡 If fewer than k nodes remain, no reversal is done.

Line:

kth = group_prev
count = 0
while kth.next and count < k:
    kth = kth.next
    count += 1

💡 Partial group at end is left as is.

reconstruct

Return new head after all reversals

Return dummy.next as the new head of the fully processed list.

💡 dummy.next points to the head of the reversed list.

Line:

return dummy.next

💡 The final list head is the start of the reversed linked list.

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

def reverseBetween(start, end):
    prev = None  # STEP 4
    curr = start  # STEP 4
    while curr != end:  # STEP 5-6, 12-13
        nxt = curr.next  # STEP 5, 12
        curr.next = prev  # STEP 5, 12
        prev = curr  # STEP 5, 12
        curr = nxt  # STEP 5, 12
    return prev  # STEP 6, 13

def reverseKGroup(head, k):
    dummy = ListNode(0)  # STEP 1
    dummy.next = head  # STEP 1
    group_prev = dummy  # STEP 1

    while True:
        kth = group_prev  # STEP 2, 9, 16
        count = 0
        while kth.next and count < k:
            kth = kth.next  # STEP 2, 9, 16
            count += 1  # STEP 2, 9, 16
        if count < k:  # STEP 16
            break
        group_next = kth.next  # STEP 3, 10

        prev = reverseBetween(group_prev.next, group_next)  # STEP 4-6, 11-13

        tmp = group_prev.next  # STEP 7, 14
        group_prev.next = prev  # STEP 7, 14
        tmp.next = group_next  # STEP 7, 14
        group_prev = tmp  # STEP 8, 15

    return dummy.next  # STEP 17

# Driver code
if __name__ == '__main__':
    nodes = [ListNode(i) for i in range(1, 6)]
    for i in range(4):
        nodes[i].next = nodes[i+1]
    new_head = reverseKGroup(nodes[0], 2)
    curr = new_head
    while curr:
        print(curr.val, end=' ')
        curr = curr.next

📊

Reverse Linked List in Groups of K (Generalization) - Watch the Algorithm Execute, Step by Step

Watching each pointer move and reversal operation helps you understand how groups are reversed without losing track of the list structure.

advance

0

→

1

→

2

→

3

→

4

→

5

advance

0

→

1

→

2

→

3

→

4

→

5

advance

0

→

1

→

2

→

3

→

4

→

5

reverse_link

0

→

1

→

2

→

3

→

4

→

5

reverse_link

0

→

1

→

2

→

3

→

4

→

5

reverse_link

0

→

1

→

2

→

3

→

4

→

5

connect

0

→

1

→

2

→

3

→

4

→

5

advance

0

→

1

→

2

→

3

→

4

→

5

advance

0

→

1

→

2

→

3

→

4

→

5

advance

0

→

1

→

2

→

3

→

4

→

5

reverse_link

0

→

1

→

2

→

3

→

4

→

5

reverse_link

0

→

1

→

2

→

3

→

4

→

5

reverse_link

0

→

1

→

2

→

3

→

4

→

5

connect

0

→

1

→

2

→

3

→

4

→

5

advance

0

→

1

→

2

→

3

→

4

→

5

compare

0

→

1

→

2

→

3

→

4

→

5

advance

2

→

1

→

4

→

3

→

5

Result: [2, 1, 4, 3, 5]

Key Takeaways

✓ Using a dummy node simplifies handling edge cases and makes pointer manipulation consistent.

Without a dummy node, reversing the head group requires special handling, which is harder to visualize.

✓ Reversing links one node at a time with prev and curr pointers clearly shows how the group reversal works.

Seeing each pointer update step-by-step reveals the in-place reversal mechanism that is not obvious from code alone.

✓ The algorithm stops reversing when fewer than k nodes remain, leaving the last partial group intact.

This decision is critical to avoid corrupting the list and is easier to understand when watching the kth pointer traversal.

Practice

1. 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

2. Identify the bug in the following code snippet implementing the optimal approach to copy a list with random pointers:

medium

A. Line assigning curr.next.random = curr.random.next misses null check for curr.random

B. In Step 3, copy_curr is never advanced, causing incorrect separation

C. In Step 1, new_node is linked incorrectly to curr.next

D. The function returns copy_head before fully separating the lists

Solution

1. Step 1: Analyze Step 3 separation loop

   copy_curr is initialized but never advanced inside the loop, so copied list links are not updated correctly.

2. Step 2: Identify fix

   Adding copy_curr = copy_curr.next inside the loop after updating copy_curr.next fixes the bug.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Without advancing copy_curr, copied list remains partially linked [OK]

Hint: Check if both original and copy pointers advance in separation loop [OK]

Common Mistakes:

• Forgetting to advance copy_curr in separation
• Assuming random pointer null checks are missing (they are present)
• Mislinking new_node in Step 1 (correct here)

3. What is the amortized time complexity of the visit, back, and forward operations in the two stacks approach for browser history, assuming n total operations?

medium

A. O(1) amortized per operation since each URL is pushed and popped at most once per stack

B. O(n) total for all operations combined, but O(1) worst-case per operation

C. O(log n) per operation due to stack resizing costs

D. O(n) per operation because each visit may clear the forward stack

Solution

1. Step 1: Analyze push/pop operations per URL

   Each URL is pushed once onto back_stack and popped at most once to forward_stack, and vice versa.

2. Step 2: Calculate amortized cost

   Since each URL moves between stacks a limited number of times, total operations over n steps average to O(1) per operation.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Amortized O(1) is standard for two stacks navigation [OK]

Hint: Each URL moves between stacks only a few times [OK]

Common Mistakes:

• Assuming clearing forward stack is O(n) per visit
• Confusing amortized with worst-case
• Ignoring stack push/pop costs

4. What is the time and space complexity of the optimal in-place odd-even linked list rearrangement algorithm for a list of length n?

medium

A. Time: O(n), Space: O(1) because each node is visited once and rearranged in-place

B. Time: O(n log n), Space: O(1) due to sorting nodes by index parity

C. Time: O(n), Space: O(n) due to auxiliary lists for odd and even nodes

D. Time: O(n^2), Space: O(1) because of nested pointer updates

Solution

1. Step 1: Identify loop iterations

   The while loop advances even and odd pointers through the list, each node visited once -> O(n) time.

2. Step 2: Analyze space usage

   No extra data structures are created; rearrangement is done by pointer manipulation -> O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time and constant space is standard for in-place linked list rearrangement [OK]

Hint: One pass with two pointers -> O(n) time, no extra lists -> O(1) space [OK]

Common Mistakes:

• Assuming nested loops cause O(n^2) time
• Confusing auxiliary space with recursion stack

5. Suppose the linked list nodes can be reused multiple times (i.e., the list is cyclic or nodes appear multiple times). Which modification to the reorder list algorithm is necessary to handle this scenario correctly?

hard

A. Use a hash set to track visited nodes and avoid infinite loops during reordering.

B. No modification needed; the recursive approach handles cycles naturally.

C. Convert the list to an array first to handle duplicates, then reorder using indices.

D. Break the list into halves without reversing the second half to prevent cycles.

Solution

1. Step 1: Understand node reuse implications

   Reusing nodes or cycles cause infinite loops if not detected during traversal.

2. Step 2: Modify algorithm to track visited nodes

   Using a hash set to track visited nodes prevents revisiting and infinite loops.

3. Step 3: Evaluate other options

   Recursive approach alone cannot detect cycles; array conversion adds overhead; skipping reversal breaks reorder logic.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Tracking visited nodes prevents infinite loops in cyclic lists [OK]

Hint: Cycle detection requires visited node tracking [OK]

Common Mistakes:

• Assuming no cycles exist
• Relying on recursion without cycle checks
• Ignoring node reuse effects