Reverse a Linked List in groups of given size 'K'

Objective: Given a linked list and integer ‘k’, write an algorithm to reverse the linked list in groups of size ‘k’.

Example:

Approach:

Earlier we have seen how to reverse a linked list, solution for reverse the linked list in groups of size will be extension of this solution.
Reverse first ‘k’ nodes of the linked list, the k^th node will be a new head, return it.
Make a recursive call to rest of the list and attach it to the last node.(See the picture below)

Complete Code:


	public class ReverseInGrps {

	public Node reveseGrps(Node head, int k){
	int x = k;
	Node head_next=null;
	Node h = head;
	Node head_prev = null;
	while(h!=null && x>0){
	head_next = h.next;
	h.next = head_prev;
	head_prev = h;
	h = head_next;
	x—;
	}
	if(head_next!=null){
	head.next = reveseGrps(head_next,k);
	}
	return head_prev;

	}

	public void display(Node head){
	Node n=head;
	while(n!=null){
	System.out.print("->" + n.data);
	n=n.next;
	}
	}
	public static void main(String[] args) {
	Node head = new Node(1);
	head.next = new Node(2);
	head.next.next = new Node(3);
	head.next.next.next = new Node(4);
	head.next.next.next.next = new Node(5);
	head.next.next.next.next.next = new Node(6);
	head.next.next.next.next.next.next = new Node(7);
	head.next.next.next.next.next.next.next = new Node(8);
	ReverseInGrps r = new ReverseInGrps();
	Node x = r.reveseGrps(head, 3);
	r.display(x);

	}

	}
	class Node{
	int data;
	Node next;
	public Node(int data){
	this.data = data;
	}
	}

Output:

->3->2->1->6->5->4->8->7

Mukul Latiyan

August 22, 2018 at 6:47 am

Hi, this code wont work, if say i have a linked list like 1->2->3->4->5 ans i want to reverse in group of 3 nodes then it will return 3->2->1->5->4 which is not correct. Can you suggest me another approach where we get 3->2->1->4->5 only.Thanks.

Reverse a Linked List in groups of given size ‘K’