Rotate Linked List block wise
Given a Linked List of length n and block length k rotate in circular manner towards right/left each block by a number d. If d is positive rotate towards right else rotate towards left.
Examples:
Input : 1->2->3->4->5->6->7->8->9->NULL,
k = 3
d = 1
Output : 3->1->2->6->4->5->9->7->8->NULL
Explanation : Here blocks of size 3 are
rotated towards right(as d is positive)
by 1.
Input : 1->2->3->4->5->6->7->8->9->10->
11->12->13->14->15->NULL,
k = 4
d = -1
Output : 2->3->4->1->6->7->8->5->10->11
->12->9->14->15->13->NULL
Explanation : Here, at the end of linked
list, remaining nodes are less than k, i.e.
only three nodes are left while k is 4.
Rotate those 3 nodes also by d.
struct node {
int data;
struct node* next;
};
node* functiondone(node* head,int k,int d){
int K=k;
int D=d;
node* temp=head;
node* forward=head;
int sign=1;
if(d<0)sign=-1;
d=d*sign;
d=d%k;
if(d==0)return head;
k=k-d;
if(sign==-1) swap(k,d);
node* ret=NULL;
if(head==NULL || !head->next)return head;
while(d&&forward->next){
forward=forward->next;
d--;
}
while(k>1&&forward->next){
forward=forward->next;
temp=temp->next;
k--;
}
if(sign==-1 && !forward->next && k>1){
int k_=K-abs(D)+d+1;
return functiondone(head,k+d,D);
}
ret=forward->next;
forward->next=head;
head=ret;
ret=temp->next;
temp->next=functiondone(head,K,D);
return ret;
}
No comments:
Post a Comment