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

3. What is the time complexity of the addAtTail operation in the optimal linked list implementation that maintains a tail pointer and size variable?

medium

A. O(n), because traversal is needed to find the tail

B. O(log n), because the list is balanced using sentinel nodes

C. O(1), because the tail pointer allows direct access to the last node

D. O(n), because updating the size requires traversal

Solution

1. Step 1: Identify operation steps

   addAtTail uses the tail pointer to append a new node directly without traversal.

2. Step 2: Analyze complexity

   Since tail pointer gives direct access, adding at tail is O(1). Size update is O(1) as it's a simple increment.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Tail pointer eliminates traversal, so addAtTail is constant time [OK]

Hint: Tail pointer enables O(1) tail insertions [OK]

Common Mistakes:

• Assuming traversal needed to find tail
• Confusing size update cost
• Thinking sentinel nodes balance list

4. Suppose the browser history must support reopening previously visited URLs multiple times without losing forward history (i.e., URLs can be revisited without clearing forward stack). Which modification to the two stacks approach correctly supports this feature?

hard

A. Use a doubly linked list with a current pointer, allowing moving back and forward without clearing forward history on visit.

B. Remove clearing of forward_stack in visit and allow duplicates in back_stack; back and forward remain unchanged.

C. Keep two stacks but add a third stack to track duplicates and manage forward history separately.

D. Use a single list with an index pointer and never slice the list on visit, allowing revisits without losing forward pages.

Solution

1. Step 1: Understand the requirement

   Revisiting URLs should not clear forward history, so forward pages must remain accessible after visit.

2. Step 2: Evaluate data structure modifications

   Two stacks approach relies on clearing forward_stack on visit, so it cannot support this without major changes. A doubly linked list with a current pointer allows moving back and forward freely without clearing forward history.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Doubly linked list supports revisits without losing forward history [OK]

Hint: Doubly linked list allows bidirectional navigation without clearing forward history [OK]

Common Mistakes:

• Removing forward_stack clearing breaks correctness in two stacks
• Adding extra stacks complicates without solving
• Single list without slicing causes stale forward pages

5. Suppose the linked list design is extended to allow negative indices in get and addAtIndex operations, where -1 refers to the last element, -2 to the second last, and so forth. Which modification correctly supports this feature without degrading average operation time complexity?

hard

A. Reject negative indices as invalid to keep implementation simple and efficient.

B. Traverse from tail backwards for negative indices to achieve O(1) access.

C. Use a doubly linked list instead of singly linked list to support backward traversal efficiently.

D. Modify get and addAtIndex to convert negative indices to positive by adding size, then proceed normally.

Solution

1. Step 1: Understand negative index semantics

   Negative indices map to positive indices by adding the list size (e.g., -1 -> size-1).

2. Step 2: Implement index normalization

   Convert negative indices to positive by adding size before performing normal operations, preserving O(n) traversal.

3. Step 3: Evaluate alternatives

   Backward traversal from tail is not possible in singly linked list; doubly linked list adds complexity and space; rejecting negatives loses functionality.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Index normalization preserves existing complexity and correctness [OK]

Hint: Normalize negative indices by adding size before operation [OK]

Common Mistakes:

• Trying backward traversal in singly linked list
• Switching to doubly linked list unnecessarily
• Ignoring negative indices