25. Reverse a doubly linked list in groups of given size

25. Reverse a doubly linked list in groups of given size

Problem link :- click here

package Linked_List;

public class LinkedList__25
{
	/*
	 	Given a doubly linked list containing n nodes. The task is to reverse every group of
	 	k nodes in the list.
	 			input :	1  2  3  4  5  6  7  8		k = 3
	 			output : 	3  2  1  6  5  4  8  7
	 			
	 	We have solved similar type of problem in Singly linked list
	 */
	
	static Node2 reverseInGroups(Node2 head, int k)
	{
		if(head == null)
			return head;
		
		head.prev = null;
		Node2 prev, cur, next;
		prev = null;
		cur = head;
		next = cur.next;
		
		int count = 0;
		while(cur != null  &&  count < k)
		{
			prev = cur;
			next = cur.next;
			cur.next = cur.prev;
			cur.prev = next;
			
			cur = cur.prev;
			count++;
		}
		if(count >= k)
			head.next = reverseInGroups(next, k);
		
		return prev;
	}
	
	public static void main(String[] args)
	{
		DoublyLinkedList list = new DoublyLinkedList();
		list.push(1);
		list.push(2);
		list.push(3);
		list.push(4);
		list.push(5);
		list.push(6);
		list.push(7);
		list.push(8);
		
		int k = 4;
		
		System.out.println("Linked list before reversing in group : ");
		list.print();
		
		list.head = reverseInGroups(list.head, k);
		System.out.println("\nLinked list after reversing in group : ");
		list.print();
	}

}

Time complexity :- O(n)
Space complexity :- O(1)