Given a doubly-linked list, rotate the linked list counter-clockwise by N nodes. Here N is a given positive integer and is smaller than the count of nodes in linked list.
N = 2
Rotated List:
Examples:
Input : a b c d e N = 2
Output : c d e a b
Input : a b c d e f g h N = 4
Output : e f g h a b c d
Asked in Amazon
Solution 1:
C++
#include<iostream>
using namespace std;
class Node
{
public :
char data;
Node* next;
Node* pre;
Node( int data)
{
this ->data=data;
pre=NULL;
next=NULL;
}
};
void insertAtHead(Node* &head, int data)
{
Node* n = new Node(data);
if (head==NULL)
{
head=n;
return ;
}
n->next=head;
head->pre=n;
head=n;
return ;
}
void insertAtTail(Node* &head, int data)
{
if (head==NULL)
{
insertAtHead(head,data);
return ;
}
Node* temp=head;
while (temp->next!=NULL)
{
temp=temp->next;
}
Node* n= new Node(data);
temp->next=n;
n->pre=temp;
return ;
}
void display(Node* head)
{
while (head!=NULL)
{
cout << head->data << " " ;
head=head->next;
}
}
void rotateByN(Node* &head, int pos)
{
if (pos==0) return ;
Node* temp=head;
while (temp->next!=NULL)
{
temp=temp->next;
}
temp->next=head;
head->pre=temp;
int count=1;
while (count<=pos)
{
head=head->next;
temp=temp->next;
count++;
}
temp->next=NULL;
head->pre=NULL;
}
int main()
{
Node* head=NULL;
insertAtTail(head, 'a' );
insertAtTail(head, 'b' );
insertAtTail(head, 'c' );
insertAtTail(head, 'd' );
insertAtTail(head, 'e' );
int n=2;
cout << "Given linked list \n" ;
display(head);
rotateByN(head,n);
cout << "\nRotated Linked list \n" ;
display(head);
cout << "\n\n" ;
return 0;
}
|
Java
import java.io.*;
import java.util.*;
class GfG {
static class Node {
char data;
Node prev;
Node next;
}
static Node head = null ;
static void rotate( int N)
{
if (N == 0 )
return ;
Node current = head;
int count = 1 ;
while (count < N && current != null ) {
current = current.next;
count++;
}
if (current == null )
return ;
Node NthNode = current;
while (current.next != null )
current = current.next;
current.next = head;
(head).prev = current;
head = NthNode.next;
(head).prev = null ;
NthNode.next = null ;
}
static void push( char new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.prev = null ;
new_node.next = (head);
if ((head) != null )
(head).prev = new_node;
head = new_node;
}
static void printList(Node node)
{
while (node != null && node.next != null ) {
System.out.print(node.data + " " );
node = node.next;
}
if (node != null )
System.out.print(node.data);
}
public static void main(String[] args)
{
push( 'e' );
push( 'd' );
push( 'c' );
push( 'b' );
push( 'a' );
int N = 2 ;
System.out.println( "Given linked list " );
printList(head);
rotate(N);
System.out.println();
System.out.println( "Rotated Linked list " );
printList(head);
}
}
|
Python3
class Node:
def __init__( self , next = None ,
prev = None , data = None ):
self . next = next
self .prev = prev
self .data = data
def push(head, new_data):
new_node = Node(data = new_data)
new_node. next = head
new_node.prev = None
if head is not None :
head.prev = new_node
head = new_node
return head
def printList(head):
node = head
print ( "Given linked list" )
while (node is not None ):
print (node.data, end = " " ),
last = node
node = node. next
def rotate(start, N):
if N = = 0 :
return
current = start
count = 1
while count < N and current ! = None :
current = current. next
count + = 1
if current = = None :
return
NthNode = current
while current. next ! = None :
current = current. next
current. next = start
start.prev = current
start = NthNode. next
start.prev = None
NthNode. next = None
return start
if __name__ = = "__main__" :
head = None
head = push(head, 'e' )
head = push(head, 'd' )
head = push(head, 'c' )
head = push(head, 'b' )
head = push(head, 'a' )
printList(head)
print ( "\n" )
N = 2
head = rotate(head, N)
printList(head)
|
C#
using System;
class GfG
{
public class Node
{
public char data;
public Node prev;
public Node next;
}
static Node head = null ;
static void rotate( int N)
{
if (N == 0)
return ;
Node current = head;
int count = 1;
while (count < N && current != null )
{
current = current.next;
count++;
}
if (current == null )
return ;
Node NthNode = current;
while (current.next != null )
current = current.next;
current.next = head;
(head).prev = current;
head = NthNode.next;
(head).prev = null ;
NthNode.next = null ;
}
static void push( char new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.prev = null ;
new_node.next = (head);
if ((head) != null )
(head).prev = new_node;
head = new_node;
}
static void printList(Node node)
{
while (node != null && node.next != null )
{
Console.Write(node.data + " " );
node = node.next;
}
if (node != null )
Console.Write(node.data);
}
public static void Main(String []args)
{
push( 'e' );
push( 'd' );
push( 'c' );
push( 'b' );
push( 'a' );
int N = 2;
Console.WriteLine( "Given linked list " );
printList(head);
rotate( N);
Console.WriteLine();
Console.WriteLine( "Rotated Linked list " );
printList(head);
}
}
|
Javascript
<script>
class Node {
constructor() {
this .data = 0;
this .prev = null ;
this .next = null ;
}
}
var head = null ;
function rotate(N) {
if (N == 0)
return ;
var current = head;
var count = 1;
while (count < N && current != null ) {
current = current.next;
count++;
}
if (current == null )
return ;
var NthNode = current;
while (current.next != null )
current = current.next;
current.next = head;
(head).prev = current;
head = NthNode.next;
(head).prev = null ;
NthNode.next = null ;
}
function push( new_data) {
var new_node = new Node();
new_node.data = new_data;
new_node.prev = null ;
new_node.next = (head);
if ((head) != null )
(head).prev = new_node;
head = new_node;
}
function printList(node) {
while (node != null && node.next != null ) {
document.write(node.data + " " );
node = node.next;
}
if (node != null )
document.write(node.data);
}
push('e ');
push(' d ');
push(' c ');
push(' b ');
push(' a');
var N = 2;
document.write( "Given linked list <br/>" );
printList(head);
rotate(N);
document.write();
document.write( "<br/>Rotated Linked list <br/>" );
printList(head);
</script>
|
Output
Before Rotation :
a-->b-->c-->d-->e-->NULL
After Rotation :
c-->d-->e-->a-->b-->NULL
Time Complexity: O(N)
Space Complexity: O(1)
Solution 2:
C++
#include<iostream>
using namespace std;
class Node
{
public :
char data;
Node* next;
Node* pre;
Node( int data)
{
this ->data=data;
pre=NULL;
next=NULL;
}
};
void insertAtHead(Node* &head, int data)
{
Node* n = new Node(data);
if (head==NULL)
{
head=n;
return ;
}
n->next=head;
head->pre=n;
head=n;
return ;
}
void insertAtTail(Node* &head, int data)
{
if (head==NULL)
{
insertAtHead(head,data);
return ;
}
Node* temp=head;
while (temp->next!=NULL)
{
temp=temp->next;
}
Node* n= new Node(data);
temp->next=n;
n->pre=temp;
return ;
}
void display(Node* head)
{
while (head!=NULL)
{
cout << head->data << "-->" ;
head=head->next;
}
cout << "NULL\n" ;
}
void rotateByN(Node *&head, int pos)
{
if (pos == 0)
return ;
Node *curr = head;
while (pos)
{
curr = curr->next;
pos--;
}
Node *tail = curr->pre;
Node *NewHead = curr;
tail->next = NULL;
curr->pre = NULL;
while (curr->next != NULL)
{
curr = curr->next;
}
curr->next = head;
head->pre = curr;
head = NewHead;
}
int main()
{
Node* head=NULL;
insertAtTail(head, 'a' );
insertAtTail(head, 'b' );
insertAtTail(head, 'c' );
insertAtTail(head, 'd' );
insertAtTail(head, 'e' );
int n=2;
cout << "\nBefore Rotation : \n" ;
display(head);
rotateByN(head,n);
cout << "\nAfter Rotation : \n" ;
display(head);
cout << "\n\n" ;
return 0;
}
|
Java
import java.util.*;
import java.io.*;
class GFG {
class Node {
char data;
Node next;
Node pre;
Node( char data)
{
this .data = data;
pre = null ;
next = null ;
}
}
Node head = null ;
public void insertAtHead( char data)
{
Node n = new Node(data);
if (head == null ) {
head = n;
return ;
}
n.next = head;
head.pre = n;
head = n;
}
public void insertAtTail( char data)
{
if (head == null ) {
insertAtHead(data);
return ;
}
Node temp = head;
while (temp.next != null ) {
temp = temp.next;
}
Node n = new Node(data);
temp.next = n;
n.pre = temp;
}
public void display()
{
Node curr = head;
while (curr != null ) {
System.out.print(curr.data + "-->" );
curr = curr.next;
}
System.out.print( "NULL\n\n" );
}
public void rotateByN( int pos)
{
if (pos == 0 ) {
return ;
}
Node curr = head;
while (pos != 0 ) {
curr = curr.next;
pos--;
}
Node tail = curr.pre;
Node NewHead = curr;
tail.next = null ;
curr.pre = null ;
while (curr.next != null ) {
curr = curr.next;
}
curr.next = head;
head.pre = curr;
head = NewHead;
}
public static void main(String[] args)
{
GFG list = new GFG();
list.insertAtTail( 'a' );
list.insertAtTail( 'b' );
list.insertAtTail( 'c' );
list.insertAtTail( 'd' );
list.insertAtTail( 'e' );
int n = 2 ;
System.out.print( "Before Rotation : \n" );
list.display();
list.rotateByN(n);
System.out.print( "After Rotation : \n" );
list.display();
}
}
|
Python3
class Node:
def __init__( self , data):
self .data = data
self .pre = None
self . next = None
class GFG:
def __init__( self ):
self .head = None
def insertAtHead( self , data):
n = Node(data)
if self .head = = None :
self .head = n
return
n. next = self .head
self .head.pre = n
self .head = n
return
def insertAtTail( self , data):
if self .head = = None :
self .insertAtHead(data)
return
temp = self .head
while temp. next ! = None :
temp = temp. next
n = Node(data)
temp. next = n
n.pre = temp
return
def display( self ):
temp = self .head
while temp ! = None :
print (temp.data, "-->" , sep = " ", end=" ")
temp = temp. next
print ( "NULL" )
def rotateByN( self , pos):
if pos = = 0 :
return
curr = self .head
while pos:
curr = curr. next
pos - = 1
tail = curr.pre
NewHead = curr
tail. next = None
curr.pre = None
while curr. next ! = None :
curr = curr. next
curr. next = self .head
self .head.pre = curr
self .head = NewHead
if __name__ = = "__main__" :
list = GFG()
list .insertAtTail( 'a' )
list .insertAtTail( 'b' )
list .insertAtTail( 'c' )
list .insertAtTail( 'd' )
list .insertAtTail( 'e' )
n = 2
print ( "Before Rotation : " )
list .display()
list .rotateByN(n)
print ( "\nAfter Rotation : " )
list .display()
print ()
|
C#
using System;
public class GFG {
class Node {
public char data;
public Node next, pre;
public Node( char data)
{
this .data = data;
pre = null ;
next = null ;
}
}
Node head = null ;
public void insertAtHead( char data)
{
Node n = new Node(data);
if (head == null ) {
head = n;
return ;
}
n.next = head;
head.pre = n;
head = n;
}
public void insertAtTail( char data)
{
if (head == null ) {
insertAtHead(data);
return ;
}
Node temp = head;
while (temp.next != null ) {
temp = temp.next;
}
Node n = new Node(data);
temp.next = n;
n.pre = temp;
}
public void display()
{
Node curr = head;
while (curr != null ) {
Console.Write(curr.data + "-->" );
curr = curr.next;
}
Console.Write( "NULL\n\n" );
}
public void rotateByN( int pos)
{
if (pos == 0) {
return ;
}
Node curr = head;
while (pos != 0) {
curr = curr.next;
pos--;
}
Node tail = curr.pre;
Node NewHead = curr;
tail.next = null ;
curr.pre = null ;
while (curr.next != null ) {
curr = curr.next;
}
curr.next = head;
head.pre = curr;
head = NewHead;
}
static public void Main()
{
GFG list = new GFG();
list.insertAtTail( 'a' );
list.insertAtTail( 'b' );
list.insertAtTail( 'c' );
list.insertAtTail( 'd' );
list.insertAtTail( 'e' );
int n = 2;
Console.Write( "Before Rotation : \n" );
list.display();
list.rotateByN(n);
Console.Write( "After Rotation : \n" );
list.display();
}
}
|
Javascript
<script>
let head = null ;
class Node {
constructor(data) {
this .data = data;
this .pre = null ;
this .next = null ;
}
};
function insertAtHead(data) {
let n = new Node(data);
if (head == null ) {
head = n;
return ;
}
n.next = head;
head.pre = n;
head = n;
return ;
}
function insertAtTail(data) {
if (head == null ) {
insertAtHead(data);
return ;
}
let temp = head;
while (temp.next != null ) {
temp = temp.next;
}
let n = new Node(data);
temp.next = n;
n.pre = temp;
return ;
}
function display(head) {
while (head != null ) {
document.write(head.data + "-->" );
head = head.next;
}
document.write( "null<br>" );
}
function rotateByN(pos) {
if (pos == 0)
return ;
let curr = head;
while (pos) {
curr = curr.next;
pos--;
}
let tail = curr.pre;
let NewHead = curr;
tail.next = null ;
curr.pre = null ;
while (curr.next != null ) {
curr = curr.next;
}
curr.next = head;
head.pre = curr;
head = NewHead;
}
insertAtTail( 'a' );
insertAtTail( 'b' );
insertAtTail( 'c' );
insertAtTail( 'd' );
insertAtTail( 'e' );
let n = 2;
document.write( "<br>Before Rotation : <br>" );
display(head);
rotateByN(head, n);
document.write( "<br>After Rotation : <br>" );
display(head);
document.write( "<br><br>" );
</script>
|
Output
Before Rotation :
a-->b-->c-->d-->e-->NULL
After Rotation :
c-->d-->e-->a-->b-->NULL
Time Complexity: O(N)
Space Complexity: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!