Reverse every K nodes

© Parineeth M R

Question 2. Reverse every k nodes in a linked list. So if the input is A->B->C->D->E->F->G->H and k is 3, then the output should be C->B->A->F->E->D->H->G


Both recursive and non-recursive solutions exist to reverse every k nodes with O(n) time complexity. Although the recursive solution takes more space, we will use it here since it is simpler. If there are n nodes in the linked list, we reverse the first k nodes and then recursively process the remaining n – k nodes. Let the linked list be A->B->C->D->E->F->G->H and k = 3. The diagram below illustrates the technique

C/C++


/* 
head: the first node of the linked list
k: how many nodes should be reversed
Return value: first node of the new linked list after reversing every k nodes
*/
struct node * k_reverse_list(struct node *head, int k)
{
	struct node *cur_node,  *prev_node, *temp_node;
	int i = 0;

	if (!head || k == 0)
		return head;

	cur_node = head;
	prev_node = NULL;

	while (cur_node && i < k) {
		/*Store the next node in a temporary variable*/
		temp_node = cur_node->next;

		/*Reverse the link */
		cur_node->next = prev_node;

		/*Update the previous node to the current node */
		prev_node = cur_node;

		/*Proceed to the next node in the original linked list*/
		cur_node = temp_node;

		++i;
	}

	/*
	We have reversed k nodes. cur_node points to the (k+1)th node
	and head points to the kth node.
	Now recursively process the remaining nodes from cur_node onwards 
	and assign the result to head->next.
	*/
	if (cur_node)
		head->next = k_reverse_list(cur_node, k);

	/*prev_node will point to first node in linked list after reversal*/
	return prev_node;
}

Java


/* 
head: first node of the linked list
k: how many nodes should be reversed
Return value: first node of the new linked list after reversing every k nodes
*/
public static LinkedListNode kReverseList(LinkedListNode head, int k) {
	int i = 0;

	if (head == null || k == 0)
		return head;

	LinkedListNode curNode = head;
	LinkedListNode prevNode = null;

	while (curNode != null && i < k) {
		/*Store the next node in a temporary variable*/
		LinkedListNode tempNode = curNode.next;

		/*Reverse the link */
		curNode.next = prevNode;

		/*Update the previous node to the current node */
		prevNode = curNode;

		/*Proceed to the next node in the original linked list*/
		curNode = tempNode;

		++i;
	}

	/*
	We have reversed k nodes. So curNode refers to the (k+1)th node.
	and head now refers to the kth node.
	Now recursively process the remaining nodes from curNode onwards 
	and assign the result to head.next.
	*/
	if (curNode != null)
		head.next = kReverseList(curNode, k);

	/*prevNode will refer to first node in linked list after reversal*/
	return prevNode;
}

Python


#head: first node of the linked list
#k: how many nodes should be reversed
#Return value: first node of the new linked list after reversing every k nodes
@staticmethod
def  k_reverse(head, k):
	if (not head or k == 0):
		return head

	cur_node = head
	prev_node = None
	i = 0
	while (cur_node and i < k): 
		#Store the next node in a temporary variable
		temp_node = cur_node.next

		#Reverse the link 
		cur_node.next = prev_node

		#Update the previous node to the current node
		prev_node = cur_node

		#Proceed to the next node in the original linked list
		cur_node = temp_node

		i += 1

	#We have reversed k nodes. So cur_node refers to the (k+1)th node
	#and head refers to the kth node.
	#Now recursively reverse the remaining nodes from cur_node onwards 
	#and assign the result to head.next.
	if (cur_node):
		head.next = LinkedListNode.k_reverse(cur_node, k)

	#prev_node will refer to first node in the linked list after reversal
	return prev_node


I hope you liked the article. I have written “The Big Book of Coding Interviews” in C/C++, Java and Python. If you are a US resident and want a free copy of the book, please send an email to

Mention the programming language of your choice in the e-mail. I will mail the Amazon Giveaway link to you. If you like the book please give your review comments on Amazon. If you didn’t like the book, please mail me what you didn’t like and I will be glad to make the required changes.

Reverse a Linked List

© Parineeth M R

Question 1. Reverse a linked list


A linked list can be reversed without using recursion by maintaining 3 nodes: prev_node, cur_node and next_node. As we traverse the linked list, we update the 3 nodes and the links in the linked list are reversed. The time complexity is O(n).

C/C++

/*Reverses the linked list without using recursion
head: first node in the original linked list 
Return value: the first node of the reversed linked list
*/
struct node* reverse_linked_list(struct node *head) {
	struct node *cur_node, *prev_node, *next_node;

	cur_node = head;
	prev_node = NULL;

	while (cur_node) {
		/*Store the next node in a temporary variable*/
		next_node = cur_node->next;

		/*Reverse the link so that current node points to the previous node*/
		cur_node->next = prev_node;

		/*Update the previous node to the current node */
		prev_node = cur_node;

		/*Proceed to the next node in the original linked list*/
		cur_node = next_node;
	}

	/*
	Once the linked list has been reversed, prev_node will be
	pointing to the new head. So return it
	*/
	return prev_node;
}

Java


/*Reverses the linked list without using recursion
head: first node in the original linked list 
Return value: the first node of the reversed linked list
*/
public static LinkedListNode reverseLinkedList(LinkedListNode head) {
	LinkedListNode curNode = head;
	LinkedListNode prevNode = null;

	while (curNode != null) {
		/*Store the next node in a temporary variable*/
		LinkedListNode nextNode = curNode.next;

		/*Reverse the link */
		curNode.next = prevNode;

		/*Update the previous node to the current node */
		prevNode = curNode;

		/*Proceed to the next node in the original linked list*/
		curNode = nextNode;
	}

	/*
	Once the linked list has been reversed, prevNode will have
	the new head. So return it
	*/
	return prevNode;
}


Python


#Reverses the linked list without using recursion
#head: first node in the original linked list 
#Return value: the first node of the reversed linked list
@staticmethod
def reverse(head):
	cur_node = head
	prev_node = None

	while (cur_node):
		#Store the next node in a temporary variable
		next_node = cur_node.next

		#Reverse the link 
		cur_node.next = prev_node

		#Update the previous node to the current node
		prev_node = cur_node

		#Proceed to the next node in the original linked list
		cur_node = next_node


	#Once the linked list has been reversed, prev_node will be
	#referring to the new head. So return it
	return prev_node



I hope you liked the article. I have written “The Big Book of Coding Interviews” in C/C++, Java and Python. If you are a US resident and want a free copy of the book, please send an email to

Mention the programming language of your choice in the e-mail. I will mail the Amazon Giveaway link to you. If you like the book please give your review comments on Amazon. If you didn’t like the book, please mail me what you didn’t like and I will be glad to make the required changes.