Here is solutions for Reverse Nodes in K-Group.

1. Understand the problem

You’re given the head of a singly linked list and an integer k.

You need to:

• Reverse nodes of the list k at a time.

• If the number of nodes remaining is less than k, leave them unchanged.

• Return the new head of the modified list

Example input:

List: 1 → 2 → 3 → 4 → 5,  k = 2
Output: 2 → 1 → 4 → 3 → 5

2. Clarify constraints, asks 4 - 5 questions including edge cases.

1. What is the value range of k?

=> Usually k ≥ 1. What happens if k = 1? (No change)

1. Can the list be empty? (head = None → return None)

2. What if k > list length? (Don’t reverse any nodes)

3. Can we have duplicate values

=> Still reverse same logic with K-group.

1. Time & space constraints?

=> Optimize to O(N) time, O(1) extra space (no recursion ideally)

3. Explore examples.

4. Brainstorm 2 - 3 solutions, naive solution first and optimize later. Explain the key idea of each solution.

4.1. Solution 1 – Naive (Count and reverse all) - Time O(N), Space O(N)

• Reverse entire list, then try to separate every k nodes.

• Time: O(N).

• Space: O(N).

4.2. Solution 2 - Recursive Solution - Time O(N), Space: O(N/k).

• At the same time, store N/k function for reverse stack.

• Time: O(N).

• Space: O(N/k).

4.3. Solution 3 - Interative Solution - Using prev, curr, next pointer - Time O(N), Space O(1).

• Idea: Using prev, curr, next pointer

• Time O(N).

• Space O(1).

5. Implement solutions.

5.1. Recursion idea - Time O(N), Space O(N / k)

1. Count k nodes forward.

2. If there are fewer than k nodes → return head (no change).

3. If we have k nodes, recursively reverse the rest of the list starting from node cur.

4. Then reverse current group one by one, linking each node to the already processed part.

5. Finally return new head of the reversed group.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        cur = head
        group = 0
        while cur and group < k:
            cur = cur.next
            group += 1

        if group == k:
            cur = self.reverseKGroup(cur, k)
            while group > 0:
                tmp = head.next
                head.next = cur
                cur = head
                head = tmp
                group -= 1
            head = cur
        return head

• Idea:

  • cur is the next segment (work like as prev).

  • head = pointer to current node within the active segment

  • cur = pointer to reversed next segment, then becomes current reversed head

reverse(6,7,8) → connect to 9
reverse(3,4,5) → connect to 6
reverse(0,1,2) → connect to 3

• Time: O(N)

• Space: O(N / k)

5.2. Interation - Time O(N), Space O(1)

Idea:

• For example: [1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9]

• prevGroup = None, curr = 1, prev = 4.

Note: vai trò của prev lúc này là nextGroup là 4.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        groupPrev = dummy

        while True:
            kth = self.getKth(groupPrev, k)
            if not kth:
                break
            groupNext = kth.next

            prev, curr = kth.next, groupPrev.next
            while curr != groupNext:
                tmp = curr.next
                curr.next = prev
                prev = curr
                curr = tmp

            tmp = groupPrev.next
            groupPrev.next = kth
            groupPrev = tmp
        return dummy.next

    def getKth(self, curr, k):
        while curr and k > 0:
            curr = curr.next
            k -= 1
        return curr

• Time: O(N).

• Space: O(1).

6. Dry run testcases.

Idea:

• For example: [1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9]

• prevGroup = None, curr = 1, prev = 4.

Note: vai trò của prev lúc này là nextGroup là 4.

Notes:

• Example for [1 -> 2 -> 3 -> 4], Dry run: 1 -> 4, 2 -> 1, 3 -> 2