# LC25. Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its 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.

For k = 2, you should return: 2->1->4->3->5 For k = 3, you should return: 3->2->1->4->5

# General idea

We will need to iterate through the linked list k at a time. We will use : … 4 -> 5 -> 6 -> 7 -> 8 -> … k = 3, and the group starts at 5 as an example

1. If we hit null before we got group of size k, we will not do anything.
2. Else we go to 3
3. Get the pointer to the node right before the beginning of the first node in group. let’s call it prev_ptr. In our example, we need to keep a pointer to 4.
4. Get the pointer to the current node, cur_ptr. In our example, a pointer to 5.
5. Reverse the linked list starting from current pointer ( in our case it is a pointer to 5), till k node after.
6. Get the pointer to the first node in the reversed linked list, new_head. It should be returned by the reverse routine.
7. Point prev_ptr to new_head and cur_ptr.next to Null
8. Call this function again with head = curr.next

# A refined and more concise general idea

While we have size k group :

1. Move forward k group to find the head of next group ( might be less than k)
3. Connect the two groups

# Code

``````    def reverseKGroup(self, head, k):
dummy = jump = ListNode(0)
dummy.next = l = r = head

while True:
count = 0
while r and count < k:   # use r to locate the range
r = r.next
count += 1

if count == k:  # if size k satisfied, reverse the inner linked list
pre, cur = r, l
for _ in range(k):
next_node = cur.next
cur.next = pre
pre = cur
cur = next_node

jump.next, jump, l = pre, l, r  # connect two k-groups
#print(jump.next.val, jump.val, l.val)
else:
return dummy.next
``````

The outer while loop will be terminated when the number of remaining nodes starting from r is fewer than k.

After the while loop that move r forward, r will point at the head of next group.

At the end of for loop, pre will contain the tail of the last group. Since the group is reversed, pre will contain the head of the reversed list.

jump is the tail of the old group. We will point jump.next it at the head of the next group, which is pre.

In the next iteration, the tail of the previous reversed group is the head of the previous unreversed group. So we point jump at l at each round.

Posted on Categories Leetcode