超难面试题，跪求答案。

超难面试题，跪求答案。在线等啊
一美资公司上机题目。
设计一个链表，要求插入和删除的时间复杂度为O(1)。而且不能使用哈西。那位高人指点一下。

------解决方案--------------------
本来连表就用来快速插入和删除的啊
------解决方案--------------------
# include "stdlib.h "
# include "malloc. h "
struct node /*节点的数据结构*/
{
int num;
char str[20];
struct node *next;
} ;
/* * * * * * * * * * * * * * * * * * * * * * * * * * * */
main( )
{
/*函数声明*/
struct node *creat();
struct node *insert();
struct node *delet();
void print( );
struct node *head;
char str[20];
int n;
head=NULL; /*做空表*/
head=creat (head); /*调用函数创建以head 为头的链表*/
p r i n t ( h e a d ) ；/*调用函数输出节点*/
printf( "\n input inserted num,name:\n ");
gets(str); /*输入学号*/
n=atoi (str);
gets(str); /*输入姓名*/
head=insert (head, str, n); 将/*节点插入链表*/
print (head)； /*调用函数输出节点*/
printf( "\n input deleted name:\n ");
gets(str); /*输入被删姓名*/
head=delet(head,str); /调*用函数删除节点*/
print (head); /*调用函数输出节点*/
r e t u r n ;
}
/* * * * * * * * * * * * * * * * * * * * * */
/* * * 创建链表* * * * * * * * * * * */
struct node *creat(struct node *head)
{
char temp[30];
struct node *pl,*p2;
pl=p2=(struct node*) malloc(sizeof(struct node));
printf ( "input num, name: \n; ")
printf( "exit:double times Enter!\n ");
g e t s ( t e m p ) ;
gets (p1-> str);
pl-> num=atoi (temp);
p l - > n e x t = N U L L ;
while (strlen (pl-> str)> 0
{
if (head==NULL) head=pl；
else p2-> next=p1;
P 2 = p l ；
pl=(struct node *)malloc(sizeof(struct node));
printf ( "input num, name: \n ");
printf( "exit:double times Enter!\n ");
g e t s ( t e m p ) ;
gets(pl -> str);
p1-> num=atoi (temp);
P 1 - > n e x t = N U L L ;
}
return head;
}
/* * * * * * * * * * * * * * * * * * * */
/* * * * * * * * * * 插入节点* * * * * * * * * */
struct node *insert (struct node *head, char *pstr,int n);
{
struct node *pl,*p2,*p3;
p1=(struct node*)malloc(sizeof(struct node));
strcpy (p1-> str, pstr);
p 1 - > n u m = n ;
p 2 = h e a d ;
if(head==NULL)
{
head=pl;pl-> next=NULL;
}
else
{
while (n> p2-> num&&p2-> next!=NULL)
{
p 3 = P 2
p 2 = p 2 - > n e x t ;
}
if (n <=p2-> num)
if (head==p2)
{
h e a d = p l ;
p l - > n e x t = p 2 ;
}
else
{
p 3 - > n e x t = p l ;
p l - > n e x t = p 2 ;
}
else
{
p 2 - > n e x t = p l ;
p l - > n e x t = N U L L ;
}
}
r e t u r n ( h e a d ) ;
}
/* * * * * * * * * * * * * * * * * * * * * * * * * /
/ * * * * * 删除节点* * * * * * * * * * * * */
struct node *delet (struct node *head, char *pstr)
{
struct node *temp,*p;
temp = head ;
if (head==NULL)
printf( "\nList is null!\n ");
else
{
temp = head ;
while (strcmp(temp-> str,pstr)!=O&&temp-> next!=NULL)
{
p = temp ;
temp=temp-> next,
}
if(strcmp(temp-> str,pstr)==0)
{
if (temp== head)
{
head=head-> next;
free( temp ) ;
}
else
{
p-> next =temp-> next;
printf( "delete string :%s\n ",temp-> str);