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


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