Microsoft Interview Question Program Managers
node* helper(node *root, int n){
node *next, *prev=0;
while(root && n--){
next= root->next;
root->next = prev;
prev = root;
root = next;
}
return prev;
}
node* reverse_no(node *cur, int c){
if(c<2 || !cur)
return cur;
node *temp, *temp1, *save;
int k=0;
for(k=c,temp=cur; k>1 && temp ; --k, temp=temp->next);
if(k!=1 || !temp)
return cur;
save=reverse_no(temp->next, c);
temp1 = helper(cur,c);
cur->next = save;
return temp1;
}
node* swap(node* head, int k)
{
if(!head||k<1) return null;
node* curr=head;
node* tail=head;
node* newHead;
node* oldTail;
for(int start=0,end=k-1;;end=end+k;)
{
tail=curr;
while(start<end)
{
if(tail->next)
{
tail=tail->next;
start++;
}
else return newHead;
}
if(!newHead)//first time
newHead=DoSwap(curr,tail);
else
oldTail->next=DoSwap(curr,tail);
oldTail=curr;
curr=curr->next;
}
return newHead;
}
node* DoSwap(node* curr, node* tail)//reverve linked list
{
node* prev=tail->next,*next;
while(curr!=tail->next)
{
next=curr->next;
curr->next=prev;
prev=curr;
curr=next;
}
return prev;
}
}
}
How to swap more than 2 elements? in wat order? If we are going 2 swap them to make them in ascending order, then w will have sorted link list in the end.
- G October 04, 2008