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
Post a Comment