Reverse Nodes in K-Group

Given the HEAD of a linked list, reverse the nodes of the list K at a time, and return  the modified list.
Imagine K like a group/window or sublist of the whole list. K is a positive integer which 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. Meaning if K=2 and the number of nodes in the Linked List is 3 then the first 2 nodes will be reversed and last one will be left as it is.

For example: In the given Linked List K=2, So the First 2 groups (i.e. first 4 nodes) are reversed but Last node remains as it is, because length of this group is less than K.

Intuition

Reversing a Linked List means the HEAD node will be TAIL and the TAIL node will be the HEAD of the Linked List. Checkout Reverse a Linked List if you've not solved how to reverse a Linked List yet. After reversing the Linked List will look like this bellow.

According to the Diagram, after reversal,

1. Kth Node Will be the New HEAD (old tail: [2]) of the Group
2. The New Tail (old head: [1]) must be connect to the next group's head.
   To do so, we need to find the Kth Node first.

Finding the Kth Node

To find the Kth Node, let's assume there was a K Group of Linked List already reversed before the actual head, like this

The DUMMY node is the TAIL of the previous K Group. Let's consider the DUMMY as the TAIL node of the previously reversed imaginary K 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]:
		dummy = ListNode(next=head)
		prev_tail = dummy
		kth_node = self.getKthNode(prev_tail, k)

Ok so how can we find the Kth Node? Let's visualize the process first, then we will write the code.

The pointer is pointing at the DUMMY HEAD. From here, the pointer needs K number of iteration to find the Kth Node

Implement a helper function to find the Kth Node.

def getKthNode(self, pointer: Optional[ListNode], k: int) -> Optional[ListNode]:
	while pointer and k > 0:
		pointer = pointer.next
		k = k - 1  # decrementing K
	return pointer  # this is the Kth node of a group

Now we've got the Kth Node and the Linked List is looking like this bellow,

The prev_tail is at the DUMMY HEAD as it was but we have a new pointer kth_node is pointing at the Tail of the Kth Group.
Now reverse the 1st K group of nodes from [1]->[2] to [2]->[1].
Keep one thing in mind that we will stop reversing when Kth node is NULL. The Kth Node can only be NULL when the number of nodes in a K Group is less than K.

while True:
	kth_node = self.getKthNode(prev_tail)
	if not kth_node:
		return

This is our base condition.

Reverse K Group of Nodes

In this section we will reverse a K group of nodes, but before further do, let's take a look at the high level workflow.

To reverse a Linked List, the current node need to be connected to it's previous node instead of it's next node. So must need a curr and prev pointer to set curr.next=prev Checkout Reverse a Linked List if you have not done it yet.

Let's take our curr pointer pointing at the HEAD and prev pointer at the Head of the next K Group. Because after reversing, Head of the current K Group will be the Tail and this Tail need to be connected to it's next Group (with the head of the next K Group), basically need to achieve this formation [DUMMY]->[2]->[1]->[3]...

As you can see, node [1] is connected to [3] (head of the next group). We will keep reversing until curr reaches to the Head of the next group which is next_group_head.

The curr pointer has reached to next_group_head, so we have reversed all nodes in the current K group. Let's implement this part of the code

	def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
		dummy = ListNode(next=head)
		prev_tail = dummy
		while True:
			kth_node = self.getKthNode(prev_tail)
			if not kth_node:
				break
			
			curr = prev_tail.next
			next_group_head = kth_node.next
			
			# Tricky part is initalizing the prev pointer.
			# we know the current Head node will be the Tail node
			# after reversing the nodes in current K Group
			# So need to link the current Head (i.e. reversed Tail eventually)
			# with the Head of the next K Group to maintain the continuety
			prev = next_group_head
			
			# reverse nodes in currnt K group
			while curr != next_group_head:
				# this part the code is actually trivial. 
				# taken from reverse linked list problem
				curr_next = curr.next
				curr.next = prev  # establishing link with the prev node
				prev = curr  # moving prev forward
				curr = curr_next  # moving curr forward
			# all nodes in the K group has reversed. what's next?

Reconcile Head of the K Group

Next part is getting ready for reversing the Next K Group. To do so, we need to shift the Tail of the Previous K Group (i.e. prev_tail pointer).

But Look like the prev_tail is still connected to the old head [1] which the new tail of the K group. This prev_tail needs to be linked with the new head [2] first.

Since prev_tail.next is going to be modified to connect with the new reversed head [2] and also need to move prev_tail to the new reversed tail [1] we have to save the Link from prev-tail to old_head in a temporary variable next_prev_tail like

next_prev_tail = prev_tail.next

Now connect prev_tail with the new reversed head [2] (reconciling the dummy head)

prev_tail.next = kth_node

Finally move the prev-tail pointer to next_prev_tail

prev_tail = next_prev_tail

Now again find the Kth node for the Next K group. We will keep finding Kth node and Reversing nodes in the K group until the Kth Node is NULL. I'm gonna skip showing diagram for 2nd K Group which will be reversed same as the 1st K group.

2nd K Group also got reversed. Find another Kth Node from the prev_tail position.

Looks like we have reached at the end, Kth node is NULL means there is no K Sized Group left to be reversed. So, We will return the reversed head of the Linked List which is dummy.next.
Let's write the whole code base altogether.

Complete Code Snippet

class Solution:
	def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
		dummy = ListNode(next=head)
		prev_tail = dummy
		while True:
			kth_node = self.getKthNode(prev_tail, k)
			if not kth_node:
				break
			curr = prev_tail.next
			next_group_head = kth_node.next
			
			# Tricky part is initalizing the prev pointer.
			# we know the current Head node will be the Tail node
			# after reversing the nodes in current K Group
			# So need to link the current Head (i.e. reversed Tail eventually)
			# with the Head of the next K Group to maintain the continuety
			prev = next_group_head
			# reverse the nodes in K group
			while curr != next_group_head:
				curr_next = curr.next
				curr.next = prev
				prev = curr
				curr = curr_next
			# all nodes in the current K group is reversed
			# link the prev_tail with the new reversed head
			next_prev_tail = prev_tail.next
			# Kth node initially was the tail which became the reversed HEAD
			prev_tail.next = kth_node
			# moving prev_tail to find the next kth node
			prev_tail = prev_tail_next
		
		# all of the K groups have been reversed.
		return dummy.next

Complexity Analysis

Time Complexity: O(N^K) where K is the number of groups. But we can drop constant for complexity analysis. So we can say the Time complexity is O(N)

Space Complexity: Constant, No extra space taken

Thanks for Stopping by! Happy Leet coding.

Connect with me on