# LeetCode #25 - Reverse Nodes In K Group

Hello LeetCode enthusiasts 👋! Today’s problem is an extension of the previous problem.

## Problem Statement

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.

• Could you solve the problem in O(1) extra memory space?
• You may not alter the values in the list’s nodes, only nodes itself may be changed.

### Constraints:

• The number of nodes in the list is in the range sz.
• 1 ≤ sz ≤ 5000
• 0 ≤ Node.val ≤ 1000
• 1 ≤ ksz

### Examples

Example 1:

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

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

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

Example 4:

Input: head = , k = 1
Output: 

## Analysis

This problem is the generalization of the previous problem LeetCode #24 — Swap Nodes In Pairs where we just needed to swap the nodes in pairs. We can also say there we need to reverse the linked lists of size two.

Here, we need to reverse the parts of the linked list of given size k. Thus, the previous problem is more like a special case of this problem where k = 2.

Here, there are two constraints — one, we cannot change the values in the nodes and two, we need to do it in constant space.

## Approach

Since this problem is the generalization of the previous problem, we can use the ideas discussed there to solve this problem.

This problem is straight-forward as we only have to take parts of the given linked lists of size k, reverse them and join them. The total size n of the given list can be represented as -

n = a.k + b

This means we need to take a sub-lists (each of size k), reverse them individually, connect them with the next list and in the end, connect all the remaining nodes as is.

### Time Complexity

We are taking k nodes at a time and reversing them. In this process, we are going through each node of the linked list only once. Thus, the time complexity will be O(n).

### Space Complexity

We are not using any data structure for intermediate computations. Hence, the space complexity will be O(1).

## Code

### Java

public class ReverseNodesInKGroup {

public ListNode reverseKGroup(ListNode head, int k) {
// Base condition
if (head == null || k == 1) {
}
ListNode dummy = new ListNode(-1);
// Point the next of this dummy to the current head
// Node to keep track of the previous node
ListNode previous = dummy;
// Variable to keep count of the nodes in the linked list
int count = 0;
// Reference to the head which will be used to traverse
while (current != null) {
count++;
if (count % k == 0) {
previous = reverse(previous, current.next);
current = previous.next;
} else {
current = current.next;
}
}
return dummy.next;
}

private ListNode reverse(ListNode start, ListNode end) {
// Previous node of the current node
ListNode previous = start.next;
// Current node
ListNode current = previous.next;
// Next node of the current node
ListNode next;
// Loop for the whole interval
while (current != end) {
// Next node of the current node
next = current.next;
// Next of current will point to the previous
current.next = start.next;
// Current node will become the previous node
start.next = current;
current = next;
}
previous.next = end;
return previous;
}
}

### Python

class ReverseNodesInKGroups:
def reverseKGroup(self, headNode: ListNode, k: int) -> Optional[ListNode]:
# Base condition
if headNode is None or k == 1:
dummy = ListNode(-1)
# Point the next of this dummy node to the current headNode
# Node to keep track of the previous node
previous = dummy
# Variable to keep count of the nodes in the linked list
count = 0
# Reference to the headNode which will be used to traverse
# Loop for all the nodes in the list
while current is not None:
count += 1
if count % k == 0:
previous = self.reverseList(previous, current.next)
current = previous.next
else:
current = current.next
return dummy.next

def reverseList(start, end):
previous = start.next
current = previous.next
while current is not end:
nextNode = current.next
current.next = start.next
start.next = current
current = nextNode
previous.next = end
return previous

### JavaScript

var reverseKGroup = function(head, k) {
// Base condition
if (head === null || k === 1) {
}
const dummy = new ListNode(-1);
// Point the next of this dummy to the current head
// Node to keep track of the previous node
let previous = dummy;
// Variable to keep count of the nodes in the linked list
let count = 0;
// Reference to the head which will be used to traverse
while (current !== null) {
count++;
if (count % k === 0) {
previous = reverse(previous, current.next);
current = previous.next;
} else {
current = current.next;
}
}
return dummy.next;
};

const reverse = (start, end) => {
// Previous node of the current node
let previous = start.next;
// Current node
let current = previous.next;
// Next node of the current node
let next;
// Loop for the whole interval
while (current != end) {
// Next node of the current node
next = current.next;
// Next of current will point to the previous
current.next = start.next;
// Current node will become the previous node
start.next = current;
current = next;
}
previous.next = end;
return previous;
}

### Kotlin

class ReverseNodesInKGroup {

fun reverseKGroup(head: ListNode?, k: Int): ListNode? {
// Base condition
if (head == null || k == 1) {
}
val dummy = ListNode(-1)
// Point the next of this dummy to the current head
// Node to keep track of the previous node
var previous = dummy
// Variable to keep count of the nodes in the linked list
var count = 0
// Reference to the head which will be used to traverse
while (current != null) {
count++
if (count % k == 0) {
previous = reverse(previous, current.next)
current = previous.next
} else {
current = current.next
}
}
return dummy.next
}

private fun reverse(start: ListNode, end: ListNode?): ListNode {
// Previous node of the current node
val previous = start.next
// Current node
var current = previous!!.next
// Next node of the current node
var next: ListNode?
// Loop for the whole interval
while (current !== end) {
// Next node of the current node
next = current!!.next
// Next of current will point to the previous
current.next = start.next
// Current node will become the previous node
start.next = current
current = next
}
previous.next = end
return previous
}
}

## Conclusion

Congratulations 👏! We have solved another linked list problem which is an extension of the previous problem.

I hope you enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn, feel free to fork 🔪 and star ⭐ it.

Till next time… Happy coding 😄 and Namaste 🙏!