美团面试算法题.doc

美团面试算法题.doc美团面试算法题
美团面试算法题
1/3
美团面试算法题
链表翻转。给出一个链表和一个数 k，比如链表 1→2→3→4→5→6，k=2，则翻转后 2→1→
4→3→6→5，若k=3,翻转后3→2→1→6→5→4，美团面试算法题
美团面试算法题
1/3
美团面试算法题
链表翻转。给出一个链表和一个数 k，比如链表 1→2→3→4→5→6，k=2，则翻转后 2→1→
4→3→6→5，若k=3,翻转后3→2→1→6→5→4，若k=4，翻转后4→3→2→1→5→6，用程序实现
structNode{
intdata;
Node*next;
};
voidreverse(Node*head,Node*end){
if(head==NULL||end==NULL)return;
Node*pre=NULL,*cur=head,*stop=end->next;
while(cur!=stop){
Node*nxt=cur->next;
cur->next=pre;
pre=cur;
cur=nxt;
}
}
15.
Node*reverseAll(Node*head,intk){
if(head==NULL||k<=0)returnNULL;
Node*cur=head;
for(inti=0;i<k-1;i++){
cur=cur->next;
if(cur==NULL)
break;
}
if(cur==NULL)returnhead;
Node*begin=cur->next,*end=begin;
Node*pre=head;
reverse(head,cur);
28.
while(begin!=NULL){
for(inti=0;i<k-1;i++){
end=end->next;
if(end==NULL)
break;
}
if(end==NULL){
pre->next=begin;
break;
}
else{
Node*nextbegin=end->next;
reverse(begin,end);
pre->next=end;
pre=begin;
begin=end=nextbegin;
}
}
returncur;
}
49.
intmain( ){
inta[]={1,2,3,4,5,6,7,8,9,10,11,12};
Node*nd[12];
for(inti=0;i<12;i++){
nd[i]=newNode;
nd[i]->next=NULL;
nd[i]->data=a[i];
}
for(inti=0;i<11;i++){
nd[i]->next=nd[i+1];
}
Node*tmp=reverseAll(nd[0],4);
for(;tmp!=NULL;tmp=tmp->