# Linked List - Reverse Nodes in K-Group

All diagrams presented herein are original creations, meticulously designed to enhance comprehension and recall. Crafting these aids required considerable effort, and I kindly request attribution if this content is reused elsewhere.

Difficulty: Easy

Similar to Swap Nodes in Pairs

## Problem

Given the `head`

of a linked list, reverse the nodes of the list `k`

at a time, and return *the modified list*.`k`

is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of `k`

then left-out nodes, in the end, should remain as it is.

**Example 1:**

1
2

Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]

**Example 2:**

1
2

Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]

## Solution

Similar to Swap Nodes in Pairs problem. We will start with the `dummy`

node

1
2

dummy = NodeList(0, head)
group_prev = dummy

**1. Find/Save Pointers**

Just like in the Swap Nodes in Pairs problem, we need to assign `group_next`

. So here we need to find the kth node (thats the last node which will be the first node in this partition).

We will write a fuction to traverse through the nodes and find the kth node.

1
2
3
4
5

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

Now the first step is to find the kth node. We will always start from `group_prev`

as thats the start of the current partition. We will also have the exit condition here is there is not enough node to create a partition of `k`

nodes.

1
2
3

kth = find_kth_node(group_prev, k)
if not kth:
break

Set the `group_next`

as the next node of `kth`

. This will not be changed as this will be a marker for how long we need to keep reversing the nodes.

1

group_next= kth.next

Start assigning `group_next`

to `prev`

as well as we want to start from reverse .

1

prev = group_next

Our `curr`

will be `group_prev.next`

.

1

curr = group_prev.next

Here is the entire setup looks like. We have not changed anything yet. Just assigned the pointers.

**2. Reverse k Nodes**

Now the task is to reverse starting from `curr`

till kth node. Lets start with the `while `

loop. There are two ways of writing this. I find the option 1 is easy to comprehend however option 2 is more generalized. Both worked in Leetcode.

**Option 1:** Use a `counter`

as we know for sure that we have `k`

nodes.

1
2
3
4

counter=k
while counter > 0:
...
counter-=1

**Option 2:** Loop till `curr`

reaches `group_next`

.

Eventhough

`group_next`

is currently same as`kth.next`

, you can not use`kth.next`

in this`while`

loop as the node`kth`

is pointing to soon be updated to point to a different node (the`kth.next`

will be updated).

1
2

while curr != group_next:
...

Save `curr.next`

to `tmp`

as `tmp`

will be reversed in next iteration. Also set `curr.next`

to `prev`

. This is the actual reversal step.

1
2

tmp = curr.next
curr.next = prev

Now we shift `prev`

to `curr`

1

prev = curr

And then point `curr`

to `tmp`

for the next iteration.

1

curr = tmp

Once the inner `while`

loop is completed, the first partition will be reversed. Next step will be to reassign the previous group.

**3. Reassign Pointers**

We need to update `group_prev`

. The new `group_prev`

will be `group_prev.next`

. However before that, we need a new `group_prev`

to be connect with previous group. (`dummy`

for the first partition.) This is an important part to understand .

Make sure to understand that this connects the last node from previous group (

`group_prev.next`

) to the first node (`kth`

) of the current group.

So lets first save current `group_prev.next`

which should be the last node in the current group.

1

tmp = group_prev.next

Now, point the `group_prev.next`

to the new first node in the current group, which was the last node in the old group before reversal.

1

group_prev.next = kth

Finally, update the `group_prev`

to point to the new last node ( i.e first node before reversal).

1

group_prev = tmp

## Final Code

Here is the full code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

def find_kth_node(curr, k):
while curr and k > 0:
curr = curr.next
k -= 1
return curr
def reverseKGroup(head, k):
dummy = ListNode(0, head)
group_prev = dummy
while True:
kth = self.find_kth_node(group_prev, k)
if not kth:
break
group_next = kth.next
prev, curr = group_next, group_prev.next,
counter = k
while counter > 0:
#while curr != group_next:
tmp = curr.next
curr.next = prev
prev = curr
curr = tmp
counter -= 1
tmp = group_prev.next
group_prev.next = kth
group_prev = tmp
return dummy.next

## Runtime Complexity

The runtime will be `O(n)`

as we are simply scanning through the list once.