Reverse Nodes in K-Group

▶

Steps

setup

Initialize dummy node and group_prev pointer

Create a dummy node with value 0 pointing to the head of the list. Set group_prev to dummy to start processing from the beginning.

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

Line:

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

💡 Dummy node allows easy reconnection of reversed groups to the list.

traverse

Find kth node from group_prev

Move kth pointer k=2 steps forward from group_prev to find the end of the current group to reverse.

💡 Identifying the kth node ensures we have enough nodes to reverse a full group.

Line:

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

💡 kth now points to the last node in the current group to reverse.

traverse

Mark group_next after kth node

Set group_next pointer to the node after kth to remember where to reconnect after reversal.

💡 group_next marks the start of the next group or remainder of the list.

Line:

group_next = kth.next

💡 Saving group_next allows reconnecting reversed group to the rest of the list.

reverse_link

Reverse first k nodes starting at group_prev.next

Call reverseLinkedList on the first k=2 nodes starting at node 1 to reverse their order.

💡 Reversing the group changes the next pointers to invert node order.

Line:

prev = reverseLinkedList(group_prev.next, k)

💡 After reversal, prev points to new head of reversed group (node 2).

connect

Reconnect reversed group to group_next

Set tail (original group head, node 1) next pointer to group_next (node 3) to reconnect reversed group to remainder.

💡 This step ensures the reversed group links correctly to the rest of the list.

Line:

tail = group_prev.next
tail.next = group_next

💡 Tail now points to the next group, maintaining list continuity.

connect

Connect group_prev to new head of reversed group

Set group_prev.next to prev (new head of reversed group, node 2) to link previous part to reversed group.

💡 This step updates the previous group's next pointer to the new head after reversal.

Line:

group_prev.next = prev

💡 The list now starts from dummy -> 2 -> 1 -> 3 ...

advance

Move group_prev to tail of reversed group

Update group_prev pointer to tail (node 1) to prepare for next group reversal.

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

Line:

group_prev = tail

💡 group_prev now points to the last node of the reversed group, anchoring next iteration.

traverse

Find kth node for second group

Move kth pointer k=2 steps forward from group_prev (node 1) to find the end of the next group.

💡 Checking if another full group of k nodes exists to reverse.

Line:

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

💡 kth points to node 4, end of second group to reverse.

traverse

Mark group_next after kth node of second group

Set group_next to node after kth (node 5) to reconnect after reversal.

💡 Remembering where to connect after reversing the second group.

Line:

group_next = kth.next

💡 group_next points to node 5, the remainder after second group.

reverse_link

Reverse second group of k nodes

Reverse the k=2 nodes starting at group_prev.next (node 3), changing their order.

💡 Reversing the second group in-place updates next pointers accordingly.

Line:

prev = reverseLinkedList(group_prev.next, k)

💡 prev points to node 4, new head of reversed second group.

connect

Reconnect reversed second group to group_next

Set tail (original head of second group, node 3) next pointer to group_next (node 5).

💡 This maintains list continuity after reversal.

Line:

tail = group_prev.next
tail.next = group_next

💡 Tail node 3 now points to node 5, linking reversed group to remainder.

connect

Connect group_prev to new head of reversed second group

Set group_prev.next to prev (node 4), linking previous part to reversed second group.

💡 This updates the list to reflect the reversed second group.

Line:

group_prev.next = prev

💡 List now has dummy -> 2 -> 1 -> 4 -> 3 -> 5

advance

Move group_prev to tail of second reversed group

Update group_prev to tail (node 3) to prepare for next iteration.

💡 Moving group_prev forward anchors next group processing.

Line:

group_prev = tail

💡 group_prev now points to node 3, the end of the second reversed group.

traverse

Attempt to find kth node for third group

Try to move kth pointer k=2 steps from group_prev (node 3) to check if full group exists.

💡 Checking if enough nodes remain for another reversal.

Line:

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

💡 Less than k nodes remain, so no reversal for last node.

reconstruct

No more full groups, return new head

Since fewer than k nodes remain, exit loop and return dummy.next as new head of fully processed list.

💡 Returning the head of the modified list completes the algorithm.

Line:

return dummy.next

💡 Final list head is node 2, reflecting all reversed groups.

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

def reverseLinkedList(head, k):
    prev = None  # STEP 4,10
    curr = head
    while k > 0:
        nxt = curr.next  # STEP 4,10
        curr.next = prev  # STEP 4,10
        prev = curr  # STEP 4,10
        curr = nxt  # STEP 4,10
        k -= 1
    return prev

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,8,14
        count = 0
        while kth.next and count < k:
            kth = kth.next  # STEP 2,8,14
            count += 1
        if count < k:
            break  # STEP 14
        group_next = kth.next  # STEP 3,9
        prev = reverseLinkedList(group_prev.next, k)  # STEP 4,10
        tail = group_prev.next  # STEP 5,11
        tail.next = group_next  # STEP 5,11
        group_prev.next = prev  # STEP 6,12
        group_prev = tail  # STEP 7,13
    return dummy.next  # STEP 15

# 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 Nodes in K-Group - Watch the Algorithm Execute, Step by Step

Watching each pointer move and reversal operation helps you understand how the algorithm manipulates the list in-place without extra memory.

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

connect

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

connect

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

reconstruct

2

→

1

→

4

→

3

→

5

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

Key Takeaways

✓ Using a dummy node simplifies edge cases and makes reconnection of reversed groups straightforward.

Without a dummy, handling the head pointer changes during reversal is tricky and error-prone.

✓ Reversing k nodes in-place requires careful pointer updates to avoid losing access to the list.

Visualizing each pointer change clarifies how the reversal preserves list integrity.

✓ The algorithm stops reversing when fewer than k nodes remain, leaving the tail portion unchanged.

This decision ensures partial groups are not reversed, which is easier to miss by just reading code.

Practice

1. You are given two non-empty singly linked lists representing two non-negative integers. The digits are stored in forward order, with the most significant digit at the head. You need to add the two numbers and return the sum as a linked list in the same forward order. Which approach guarantees an optimal solution without modifying the input lists or using extra space proportional to the number of digits?

easy

A. Reverse both lists, add digits from least significant to most significant, then reverse the result.

B. Use a greedy approach to add digits from left to right without padding or recursion.

C. Pad the shorter list with zeros, recursively add corresponding nodes from the most significant digit, and propagate carry backward.

D. Convert both lists to integers, add them, then convert the sum back to a linked list.

Solution

1. Step 1: Understand the problem constraints

   The digits are stored in forward order, so addition must start from the most significant digit. Direct addition from head to tail requires alignment of list lengths.

2. Step 2: Identify the approach that handles alignment and carry correctly

   Padding the shorter list ensures both lists have equal length. Recursively adding nodes from the most significant digit allows carry to propagate backward naturally without reversing or extra space.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Padding + recursion handles carry and alignment correctly [OK]

Hint: Pad shorter list and recurse from MSB [OK]

Common Mistakes:

• Reversing lists modifies inputs unexpectedly
• Greedy addition fails due to carry propagation
• Converting to integers causes overflow or inefficiency

2. You are given k sorted linked lists and need to merge them into one sorted linked list efficiently. Which approach guarantees the optimal time complexity for this problem?

easy

A. Merge all lists into one array, then sort the array and rebuild the linked list.

B. Use dynamic programming to store intermediate merged results and avoid repeated merges.

C. Use a min-heap (priority queue) to repeatedly extract the smallest node among the heads of the lists.

D. Merge the lists one by one sequentially, merging two lists at a time from left to right.

Solution

1. Step 1: Understand problem constraints

   We have k sorted linked lists and want to merge them efficiently.

2. Step 2: Compare approaches

   Brute force sorting all nodes is O(N log N). Sequential merges cost O(kN). Min-heap approach extracts smallest node in O(log k) time, total O(N log k), which is optimal.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Min-heap approach uses priority queue to achieve O(N log k) [OK]

Hint: Min-heap merges k lists in O(N log k) time [OK]

Common Mistakes:

• Thinking sequential merges are optimal
• Assuming sorting all nodes is best
• Confusing DP with merge approach

3. You are given a singly linked list and need to determine if it reads the same forwards and backwards without using extra space proportional to the list size. Which approach best guarantees an optimal solution in terms of time and space complexity?

easy

A. Convert the linked list to an array and check if the array is a palindrome.

B. Use a dynamic programming approach to store palindrome states for sublists.

C. Use a recursive two-pointer technique that compares nodes from front and back simultaneously.

D. Use a greedy approach by comparing nodes pairwise from start and end without recursion or extra space.

Solution

1. Step 1: Understand the problem constraints

   The problem requires checking palindrome property in a linked list without using extra space proportional to the list size, ruling out array conversion.

2. Step 2: Analyze space and time complexity of options

   Convert the linked list to an array and check if the array is a palindrome. uses O(n) extra space for array; Use a dynamic programming approach to store palindrome states for sublists. uses O(n^2) time and space; Use a recursive two-pointer technique that compares nodes from front and back simultaneously. uses O(n) time but O(n) space due to recursion stack; Use a greedy approach by comparing nodes pairwise from start and end without recursion or extra space. uses O(n) time and O(1) space by reversing the second half and comparing.

3. Step 3: Identify optimal approach

   Use a greedy approach by comparing nodes pairwise from start and end without recursion or extra space. is optimal with O(n) time and O(1) space, meeting constraints without recursion overhead.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Greedy pairwise comparison with in-place reversal is optimal [OK]

Hint: In-place reversal of second half achieves O(1) space palindrome check [OK]

Common Mistakes:

• Assuming recursion uses no extra space
• Confusing DP with palindrome linked list
• Thinking array conversion is space optimal

4. What is the time complexity of the optimal recursive solution that pads the shorter list and recursively adds two linked lists representing numbers in forward order, each of length n and m respectively?

medium

A. O(n + m)

B. O(max(n, m))

C. O(max(n, m) * log(max(n, m)))

D. O(n * m)

Solution

1. Step 1: Analyze list traversal and padding

   Getting lengths and padding shorter list takes O(n + m) time.

2. Step 2: Analyze recursive addition

   Recursion visits each node once, total O(max(n, m)) steps.

3. Step 3: Simplify complexity

   Since padding and traversal are linear, total time complexity is O(max(n, m)).

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Each node processed once, no nested loops [OK]

Hint: Single pass plus padding is linear [OK]

Common Mistakes:

• Mistaking recursion stack as extra multiplicative factor
• Confusing with quadratic due to nested loops
• Assuming log factor from recursion depth

5. Identify the bug in the following code snippet that attempts to delete a node from a singly linked list given only access to that node.

def deleteNode(node):
    node.val = node.next.val
    # Missing update of next pointer

What is the consequence of this bug?

medium

A. The list will contain duplicate values and the node is not truly deleted.

B. The node is correctly deleted with no issues.

C. The code will raise a runtime error due to null pointer dereference.

D. The node will be set to None, breaking the list.

Solution

1. Step 1: Analyze the code's effect

   Only the node's value is overwritten with the next node's value, but the next pointer is not updated.

2. Step 2: Understand the consequence

   Since next pointer is unchanged, the next node remains in the list, causing duplicate values and no actual deletion.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Next pointer must be updated to remove next node [OK]

Hint: Must update next pointer after copying value [OK]

Common Mistakes:

• Forgetting to update next pointer after copying value
• Assuming setting node to None deletes it
• Trying to delete tail node with this method