每日微软面试题

每日微软面试题——day 1

<以下微软面试题全来自网络>

<以下答案与分析纯属个人观点，不足之处，还望不吝指出^_^>

题：.编写反转字符串的程序，要求优化速度、优化空间。

分析：构建两个迭代器p 和 q ，在一次遍历中，p的位置从字串开头向中间前进，q从字串末尾向中间后退，反转字串只要每次遍历都交换p和q所指向的内容即可，直到p和q在中间相遇，这时循环次数刚好等于 字串的长度/2。

实现代码：

/**
author:花心龟
blog：http://blog.csdn.net/zhanxinhang
**/

#include<stdio.h>
voidreverse(char*_str,int_l)//反转函数,_l指要反转字串的长度
{
char*p=_str,*q=_str+_l-1,temp;

while(q>p)
{
temp=*p;
*p=*q;
*q=temp;

p++;
q--;
}
}

intmain()
{
charstr0[11]="0123456789";
reverse(str0,sizeof(str0)-1);
printf("str0=%s\n",str0);

charstr1[6]="01234";
reverse(str1,sizeof(str1)-1);
printf("str1=%s",str1);
return0;
}

题：.在链表里如何发现循环链接？

分析：可以构建两个迭代器p和pp，p一次向移动一个节点，pp一次移动两个节点，如果p和pp在某个时刻指向了同一个节点，那么该链表就有循环链接。

实现代码：

/**
Author:花心龟
Blog：http://blog.csdn.net/zhanxinhang
**/
#include<stdio.h>
#include<malloc.h>

#defineTEST

structlist_node
{
intdata;
list_node*next;
};
list_node*head;//指向头结点

voidlist_create()
{
inti;
list_node*p=NULL;
head=(list_node*)malloc(sizeof(list_node));
head->data=0;//头结点数据设为
head->next=NULL;

p=head;
for(i=1;i<6;i++)//创建个结点
{
p->next=(list_node*)malloc(sizeof(list_node));
p->next->data=i;
p->next->next=NULL;
p=p->next;
}
p->next=head;//使尾结点的下一个结点指针指向头结点，构成循环链表

#ifdefTEST
p=head;
for(i=0;i<12&&p!=NULL;i++)
{
printf("%d",p->data);
p=p->next;
}
printf("\n");
#endif
}

voidcycleList_test()
{
if(head==NULL||head->next==NULL)
return;
list_node*p=NULL,*pp=NULL;
p=head;
pp=head->next->next;
while(p!=pp)
{
p=p->next;
pp=pp->next->next;

if(p==NULL||pp==NULL)
{
printf("不是循环链表");
return;
}
}
printf("是循环链表");
}

voidlist_destroy()
{
list_node*pmove=NULL,*pdel=NULL;
pmove=head->next;

while(pmove!=head)
{
pdel=pmove;
pmove=pmove->next;
free(pdel);
}

free(head);
}
intmain()
{
list_create();//构建循环链表
cycleList_test();//测试是否是循环链表
list_destroy();//销毁链表
return0;
}