© 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