24. Rotate doubly linked list by N nodes

24. Rotate doubly linked list by N nodes


Problem link :- click here


package Linked_List;

public class LinkedList__24
{
	/*
		Given a doubly linked list, rotate the linked list counter-clockwise(left) by 'n' nodes.
		Here 'n' is a given positive integer and is smaller than the count of nodes in linked
		list.
				input : 	a  b  c  d  e	n = 2
				output : 	c  d  e  a  b 
		
		1 -> Lets take first, second & last nodes.
		2 -> iterate 'n' times in the list
		3 -> move the first node to the last
			last.next = first;
			first.prev = last;
			first.next = null;
			
		4 -> update the first, second & last node for the next iteration 
			first = second;;
			second = second.next;
			last = last.next;
			
		5 -> update the head of the list
	 */
	
	static void rotateLeft(DoublyLinkedList list, int n)
	{
		//step 1 :-
		Node2 first, second, last;
		first = list.head;
		second = first.next;
		last = list.head;
		while(last.next != null)
			last = last.next;
		
		//step 2 :- 
		for(int i=0; i<n; i++)
		{
			//step 3 :-
			last.next = first;
			first.prev = last;
			first.next = null;
			
			//step 4 :-
			first = second;
			second = second.next;
			last = last.next;
		}
		
		//step 5 :- 
		list.head = first;
	}
	
	
	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);
		
		int n = 2;
		
		System.out.println("Linked list before rotating : ");
		list.print();
		
		rotateLeft(list, n);
		System.out.println("\nLinked list after rotating : ");
		list.print();
	}

}

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

Comments

Popular posts from this blog

4.Sort an array of 0's, 1's & 2's.

1. Reverse

3. Height of Binary tree