Rotate Linked List block wise - cook the code

Saturday 27 January 2018

Rotate Linked List block wise


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.
code implementation:- 
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