Reverse a Linked List in groups of given size
Reverse a Linked List in groups of given size
This article will explain how to reverse a linked list in groups of given size. Here we have given a linked list and we need to reverse every k nodes of the given linked list.
Example:
Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> NULL, K = 3
Output: 3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 8 -> 7 -> NULL
Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> NULL, K = 5
Output: 5 -> 4 -> 3 -> 2 -> 1 -> 8 -> 7 -> 6 -> NULL
Algorithm:
- Firstly, we will count the total number of nodes present in the given linked list.
- Then, we will try to find the total number of reversal is required with the help of the total number of nodes divides by the value of k.
- After this, we will apply the algorithm to reverse the singly linked list and return the head or starting pointer of the resultant linked list.
Source code to reverse the linked list in group size using Java
import java.util.*;
import java.lang.*;
class Node
{
int data;
Node next;
Node(int key)
{
data = key;
next = null;
}
}
public class Main
{
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter the total no of elements for linked list:");
int n = sc.nextInt();
System.out.println("Enter the elements for linked list:");
int a1 = sc.nextInt();
Node head = new Node(a1);
Node tail = head;
for(int i = 1; i < n; i++)
{
int a = sc.nextInt();
tail.next = new Node(a);
tail = tail.next;
}
System.out.println("Enter the value of k:");
int k = sc.nextInt();
ReverseInSize ob = new ReverseInSize ();
Node res = ob.reverse(head, k);
printList(res);
System.out.println();
}
public static void printList(Node node)
{
System.out.println("The resultant linked list is:");
while(node != null)
{
System.out.print(node.data + " ");
node = node.next;
}
}
}
//Driver Code Ends
class ReverseInSize
{
// For reverse the linked list in groups of a given size
public static Node reverse(Node head, int k)
{
Node temp = head;
Node resultant = null;
int count = 0;
// For counting the total no of nodes present in the given linked list
while(temp != null)
{
count++;
temp = temp.next;
}
if(count%k == 0)
{
count = count/k;
}
else
count = (count/k)+1;
temp = head;
while(count-- > 0)
{
int c = k;
Node next = null;
Node pre = null;
Node curr = head;
while(c-- > 0 && head != null)
head = head.next;
c = k;
// For reverse the linked list
while(c-- > 0 && curr != null)
{
next = curr.next;
curr.next = pre;
pre = curr;
curr = next;
}
c = k;
if(resultant == null)
resultant = pre;
else
{
Node tt = resultant;
while(tt.next != null)
{
tt = tt.next;
}
tt.next = pre;
}
}
return resultant;
}
}
Output: -
Complexity Analysis:
Time Complexity: The time complexity of this method is O(n).