# 面试题14：用O(1)时间删除链表结点

```/*     获取要删除的结点    */
{
int count;
cout << "请输入你要删除的结点： ";
cin >> count;
int i = 0;
while( i <count)
{
p = p->next;
i++;
}
return p;
}

/*     o(1)时间删除链表结点    */
{
if(head == NULL || pToBeDeleted == NULL)
return;

//要删除的结点不是尾结点
if(pToBeDeleted ->next != NULL)
{
Node *pnext = pToBeDeleted->next;
pToBeDeleted->data = pnext->data;
pToBeDeleted->next = pnext->next;
free(pnext);
pnext = NULL;
}
//链表只有一个结点，删除头结点（也是尾结点）
{
free(pToBeDeleted);
pToBeDeleted = NULL;
}
//链表中有多个结点，要删除的结点是尾结点
else
{
while(pNode->next != pToBeDeleted)
{
pNode = pNode->next;
}
pNode->next = NULL;
free(pToBeDeleted);
pToBeDeleted = NULL;
}
}```

```#include<iostream>
#include <stack>
#include<stdlib.h>
#include<time.h>

using namespace std;

typedef struct node
{
int data;
struct node *next;
}Node;

/*     创建含有n个结点的单链表    */
{

/* 初始化随机数种子 */
srand(time(0));  //srand函数在stdlib.h头文件中，time函数在time.h头文件中

for(int i=0; i < n; i++)
{
Node *p = (Node *)malloc(sizeof(Node));
p->data = rand()%100+1;  //随机生成100以内的数字
p->next = q->next;
q->next = p;
q = p;
}
q->next = NULL;

}

/****打印单链表******/
{
Node *p;
{
cout << "The LinkList is Empty !" <<endl;
return;
}
while(p!=NULL)
{
cout << p->data << " " ;
p=p->next;
}
}
/*     获取要删除的结点    */
{
int count;
cout << "请输入你要删除的结点： ";
cin >> count;
int i = 0;
while( i <count)
{
p = p->next;
i++;
}
return p;
}

/*     o(1)时间删除链表结点    */
{
if(head == NULL || pToBeDeleted == NULL)
return;

//要删除的结点不是尾结点
if(pToBeDeleted ->next != NULL)
{
Node *pnext = pToBeDeleted->next;
pToBeDeleted->data = pnext->data;
pToBeDeleted->next = pnext->next;
free(pnext);
pnext = NULL;
}
//链表只有一个结点，删除头结点（也是尾结点）
{
free(pToBeDeleted);
pToBeDeleted = NULL;
}
//链表中有多个结点，要删除的结点是尾结点
else
{
while(pNode->next != pToBeDeleted)
{
pNode = pNode->next;
}
pNode->next = NULL;
free(pToBeDeleted);
pToBeDeleted = NULL;
}
}
int main()
{
int length;

cin >> length;
cout << "The new created LinkList as below: " ;
cout << endl;

Node *toBedeletedNode;
cout << "删除了你要删除的结点后的链表为： ";