Given a linked list and an integer K, the task is to reverse every K nodes of the given linked list.
Examples:
Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> NULL, K = 3
Output: 3 2 1 6 5 4 8 7Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> NULL, K = 5
Output: 5 4 3 2 1 8 7 6
Approach: We have already discussed a recursive solution in the posts Set 1 and Set 2. In this post, we will discuss an iterative solution to the above problem. Unlike the above solutions, we do not use any form of the stack to implement our solution. We reverse the first k nodes of the linked list. While reversing, we keep track of the first and last node of the k-reversed linked list using the join and tail pointer. After reversing the k nodes of the linked list, we join the nodes pointed by the tail pointer and join pointer and update them. We repeat this process until all groups of nodes are reversed.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Link list nodestruct Node { int data; struct Node* next;};/* Function to reverse the linked list in groups of size k and return the pointer to the new head node. */Node* reverse(struct Node* head, int k){ Node* prev = NULL; Node* curr = head; Node* temp = NULL; Node* tail = NULL; Node* newHead = NULL; Node* join = NULL; int t = 0; // Traverse till the end of the linked list while (curr) { t = k; join = curr; prev = NULL; // Reverse group of k nodes of the linked list while (curr && t--) { temp = curr->next; curr->next = prev; prev = curr; curr = temp; } // Sets the new head of the input list if (!newHead) newHead = prev; /* Tail pointer keeps track of the last node of the k-reversed linked list. We join the tail pointer with the head of the next k-reversed linked list's head */ if (tail) tail->next = prev; /* The tail is then updated to the last node of the next k-reverse linked list */ tail = join; } /* newHead is new head of the input list */ return newHead;}// Function to insert a node at// the head of the linked listvoid push(Node** head_ref, int new_data){ /* allocate node */ Node* new_node = new Node(); /* put in the data */ new_node->data = new_data; /* link the old list of the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node;}// Function to print the linked listvoid printList(Node* node){ while (node != NULL) { cout << node->data << " "; node = node->next; }}// Driver codeint main(){ // Start with the empty list Node* head = NULL; // Created Linked list is // 1->2->3->4->5->6->7->8->9 push(&head, 9); push(&head, 8); push(&head, 7); push(&head, 6); push(&head, 5); push(&head, 4); push(&head, 3); push(&head, 2); push(&head, 1); int k = 3; cout << "Given linked list \n"; printList(head); head = reverse(head, k); cout << "\nReversed Linked list \n"; printList(head); return (0);} |
Java
// Java implementation of the approach class GFG{ // Link list node static class Node { int data; Node next; }; // Function to reverse the linked list in groups of //size k and return the pointer to the new head node. /static Node reverse( Node head, int k) { Node prev = null; Node curr = head; Node temp = null; Node tail = null; Node newHead = null; Node join = null; int t = 0; // Traverse till the end of the linked list while (curr != null) { t = k; join = curr; prev = null; // Reverse group of k nodes of the linked list while (curr != null && t-- != 0) { temp = curr.next; curr.next = prev; prev = curr; curr = temp; } // Sets the new head of the input list if ((newHead == null)) newHead = prev; /* Tail pointer keeps track of the last node of the k-reversed linked list. We join the tail pointer with the head of the next k-reversed linked list's head */ if (tail != null) tail.next = prev; /* The tail is then updated to the last node of the next k-reverse linked list */ tail = join; } // newHead is new head of the input list / return newHead; } // Function to insert a node at // the head of the linked list static Node push(Node head_ref, int new_data) { // allocate node / Node new_node = new Node(); // put in the data / new_node.data = new_data; // link the old list of the new node / new_node.next = (head_ref); // move the head to point to the new node / (head_ref) = new_node; return head_ref;} // Function to print the linked list static void printList(Node node) { while (node != null) { System.out.print( node.data + " "); node = node.next; } } // Driver code public static void main(String args[]){ // Start with the empty list Node head = null; // Created Linked list is // 1.2.3.4.5.6.7.8.9 head = push(head, 9); head = push(head, 8); head = push(head, 7); head = push(head, 6); head = push(head, 5); head = push(head, 4); head = push(head, 3); head = push(head, 2); head = push(head, 1); int k = 3; System.out.print( "Given linked list \n"); printList(head); head = reverse(head, k); System.out.print( "\nReversed Linked list \n"); printList(head); }} // This code is contributed by Arnab Kundu |
Python3
# Python3 implementation of the approach import math# Link list node class Node: def __init__(self, data): self.data = data self.next = None# Function to reverse the linked list in groups of #size k and return the pointer to the new head node. def reverse(head, k) : prev = None curr = head temp = None tail = None newHead = None join = None t = 0 # Traverse till the end of the linked list while (curr) : t = k join = curr prev = None # Reverse group of k nodes of the linked list while (curr and t > 0): temp = curr.next curr.next = prev prev = curr curr = temp t = t - 1 # Sets the new head of the input list if (newHead == None): newHead = prev # Tail pointer keeps track of the last node # of the k-reversed linked list. We join the # tail pointer with the head of the next # k-reversed linked list's head if (tail != None): tail.next = prev # The tail is then updated to the last node # of the next k-reverse linked list tail = join # newHead is new head of the input list */ return newHead # Function to insert a node at # the head of the linked list def push(head_ref, new_data) : # allocate node */ new_node =Node(new_data) # put in the data */ new_node.data = new_data # link the old list of the new node */ new_node.next = head_ref # move the head to point to the new node */ head_ref = new_node return head_ref# Function to print the linked list def printList(node): while (node != None) : print(node.data, end = " ") node = node.next # Driver code if __name__=='__main__': # Start with the empty list head = None # Created Linked list is # 1.2.3.4.5.6.7.8.9 head = push(head, 9) head = push(head, 8) head = push(head, 7) head = push(head, 6) head = push(head, 5) head = push(head, 4) head = push(head, 3) head = push(head, 2) head = push(head, 1) k = 3 print("Given linked list ") printList(head) head = reverse(head, k) print("\nReversed Linked list ") printList(head) # This code is contributed by Srathore |
C#
// C# implementation of the approach using System; class GFG{ // Link list node public class Node { public int data; public Node next; }; // Function to reverse the linked list in groups of //size k and return the pointer to the new head node. /static Node reverse( Node head, int k) { Node prev = null; Node curr = head; Node temp = null; Node tail = null; Node newHead = null; Node join = null; int t = 0; // Traverse till the end of the linked list while (curr != null) { t = k; join = curr; prev = null; // Reverse group of k nodes of the linked list while (curr != null && t-- != 0) { temp = curr.next; curr.next = prev; prev = curr; curr = temp; } // Sets the new head of the input list if ((newHead == null)) newHead = prev; /* Tail pointer keeps track of the last node of the k-reversed linked list. We join the tail pointer with the head of the next k-reversed linked list's head */ if (tail != null) tail.next = prev; /* The tail is then updated to the last node of the next k-reverse linked list */ tail = join; } // newHead is new head of the input list / return newHead; } // Function to insert a node at // the head of the linked list static Node push(Node head_ref, int new_data) { // allocate node / Node new_node = new Node(); // put in the data / new_node.data = new_data; // link the old list of the new node / new_node.next = (head_ref); // move the head to point to the new node / (head_ref) = new_node; return head_ref;} // Function to print the linked list static void printList(Node node) { while (node != null) { Console.Write( node.data + " "); node = node.next; } } // Driver code public static void Main(String []args){ // Start with the empty list Node head = null; // Created Linked list is // 1.2.3.4.5.6.7.8.9 head = push(head, 9); head = push(head, 8); head = push(head, 7); head = push(head, 6); head = push(head, 5); head = push(head, 4); head = push(head, 3); head = push(head, 2); head = push(head, 1); int k = 3; Console.Write( "Given linked list \n"); printList(head); head = reverse(head, k); Console.Write( "\nReversed Linked list \n"); printList(head); }} // This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation of the approach // Link list node class Node { constructor() { this.data = 0; this.next = null; }}; // Function to reverse the linked list// in groups of size k and return the// pointer to the new head node. function reverse(head, k) { var prev = null; var curr = head; var temp = null; var tail = null; var newHead = null; var join = null; var t = 0; // Traverse till the end of the linked list while (curr != null) { t = k; join = curr; prev = null; // Reverse group of k nodes of the linked list while (curr != null && t-- != 0) { temp = curr.next; curr.next = prev; prev = curr; curr = temp; } // Sets the new head of the input list if ((newHead == null)) newHead = prev; /* Tail pointer keeps track of the last node of the k-reversed linked list. We join the tail pointer with the head of the next k-reversed linked list's head */ if (tail != null) tail.next = prev; /* The tail is then updated to the last node of the next k-reverse linked list */ tail = join; } // newHead is new head of the input list return newHead; } // Function to insert a node at // the head of the linked list function push(head_ref, new_data) { // Allocate node var new_node = new Node(); // Put in the data new_node.data = new_data; // Link the old list of the new node new_node.next = (head_ref); // Move the head to point to the new node (head_ref) = new_node; return head_ref;} // Function to print the linked list function printList(node) { while (node != null) { document.write( node.data + " "); node = node.next; } } // Driver code // Start with the empty list var head = null; // Created Linked list is // 1.2.3.4.5.6.7.8.9 head = push(head, 9); head = push(head, 8); head = push(head, 7); head = push(head, 6); head = push(head, 5); head = push(head, 4); head = push(head, 3); head = push(head, 2); head = push(head, 1); var k = 3; document.write("Given linked list <br>"); printList(head); head = reverse(head, k);document.write("<br>Reversed Linked list <br>"); printList(head); // This code is contributed by itsok</script> |
Output:
Given linked list 1 2 3 4 5 6 7 8 9 Reversed Linked list 3 2 1 6 5 4 9 8 7
Time Complexity: O(n) where n is the number of nodes in the given list.
Space Complexity: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
