删除单链表指定的某个结点是单链表的一个基本操作。删除操作大致分为如下三种：

1. 删除p所指向结点的后继结点（假设存在）
2. 删除p所指向的结点。
3. 删除线性表中值为x的数据元素。

大致算法思想：删除运算是将表的第i个结点删去。

具体步骤： 

1. 找到a_i-1的存储位置p（因为在单链表中结点a_i的存储地址是在其直接前趋结点a_i-1的指针域next中）
2. 令p-＞next指向a_i的直接后继结点（即把a_i从链上摘下）
3. 释放结点a_i的空间，将其归还给“存储池”。

具体代码实现如下：

/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
Status ListDelete(LinkList *L,int i,ElemType *e)
{
	int j;
	LinkList p,q;
	p = *L;
	j = 1;
	while (p->next && j < i)	/* 遍历寻找第i个元素 */
	{
        p = p->next;
        ++j;
	}
	if (!(p->next) || j > i)
	    return ERROR;           /* 第i个元素不存在 */
	q = p->next;
	p->next = q->next;			/* 将q的后继赋值给p的后继 */
	*e = q->data;               /* 将q结点中的数据给e */
	free(q);                    /* 让系统回收此结点，释放内存 */
	return OK;
}

下面是动画演示：

设单链表的长度为n，则删去第i个结点仅当1≤i≤n时是合法的。

当i=n+1时，虽然被删结点不存在，但其前趋结点却存在，它是终端结点。因此被删结点的直接前趋*p存在并不意味着被删结点就一定存在，仅当*p存在（即p！=NULL）且*p不是终端结点（即p-＞next！=NULL）时，才能确定被删结点存在。

完整的可执行代码如下：

#include "stdio.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */

typedef struct Node
{
    ElemType data;
    struct Node *next;
}Node;
typedef struct Node *LinkList; /* 定义LinkList */

Status visit(ElemType c)
{
    printf("%d ",c);
    return OK;
}

/* 初始化顺序线性表 */
Status InitList(LinkList *L)
{
    *L=(LinkList)malloc(sizeof(Node)); /* 产生头结点,并使L指向此头结点 */
    if(!(*L)) /* 存储分配失败 */
            return ERROR;
    (*L)->next=NULL; /* 指针域为空 */

    return OK;
}

/* 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 */
int ListLength(LinkList L)
{
    int i=0;
    LinkList p=L->next; /* p指向第一个结点 */
    while(p)
    {
        i++;
        p=p->next;
    }
    return i;
}

/* 初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
Status ListTraverse(LinkList L)
{
    LinkList p=L->next;
    while(p)
    {
        visit(p->data);
        p=p->next;
    }
    printf("\n");
    return OK;
}

/*  随机产生n个元素的值，建立带表头结点的单链线性表L（头插法） */
void CreateListHead(LinkList *L, int n)
{
	LinkList p;
	int i;
	srand(time(0));                         /* 初始化随机数种子 */
	*L = (LinkList)malloc(sizeof(Node));
	(*L)->next = NULL;                      /*  先建立一个带头结点的单链表 */
	for (i=0; i < n; i++)
	{
		p = (LinkList)malloc(sizeof(Node)); /*  生成新结点 */
		p->data = rand()%100+1;             /*  随机生成100以内的数字 */
		p->next = (*L)->next;
		(*L)->next = p;						/*  插入到表头 */
	}
}

/*  随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法） */
void CreateListTail(LinkList *L, int n)
{
	LinkList p,r;
	int i;
	srand(time(0));                      /* 初始化随机数种子 */
	*L = (LinkList)malloc(sizeof(Node)); /* L为整个线性表 */
	r=*L;                                /* r为指向尾部的结点 */
	for (i=0; i < n; i++)
	{
		p = (Node *)malloc(sizeof(Node)); /*  生成新结点 */
		p->data = rand()%100+1;           /*  随机生成100以内的数字 */
		r->next=p;                        /* 将表尾终端结点的指针指向新结点 */
		r = p;                            /* 将当前的新结点定义为表尾终端结点 */
	}
	r->next = NULL;                       /* 表示当前链表结束 */
}

/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
Status ListDelete(LinkList *L,int i,ElemType *e)
{
	int j;
	LinkList p,q;
	p = *L;
	j = 1;
	while (p->next && j < i)	/* 遍历寻找第i个元素 */
	{
        p = p->next;
        ++j;
	}
	if (!(p->next) || j > i)
	    return ERROR;           /* 第i个元素不存在 */
	q = p->next;
	p->next = q->next;			/* 将q的后继赋值给p的后继 */
	*e = q->data;               /* 将q结点中的数据给e */
	free(q);                    /* 让系统回收此结点，释放内存 */
	return OK;
}

int main()
{
    LinkList L;
    Status i;
    char opp;
    ElemType e;
    int find;
    int tmp;

    i=InitList(&L);
    printf("初始化L后：ListLength(L)=%d\n",ListLength(L));

    printf("\n1.查看链表 \n2.创建链表（尾插法） \n3.链表长度 \n4.删除结点 \n0.退出 \n请选择你的操作：\n");
    while(opp != '0'){
        scanf("%c",&opp);
        switch(opp){
            case '1':
                ListTraverse(L);
                printf("\n");
                break;

            case '2':
                CreateListTail(&L,20);
                printf("整体创建L的元素(尾插法)：\n");
                ListTraverse(L);
                printf("\n");
                break;

            case '3':
                //clearList(pHead);   //清空链表
                printf("ListLength(L)=%d \n",ListLength(L));
                printf("\n");
                break;

            case '4':
                printf("需要删除第几个结点？\n");
                scanf("%d", &find);
                ListDelete(&L,find,&e);
                ListTraverse(L);
                printf("\n");
                break;

            case '0':
                exit(0);
        }
    }

}

删除结点算法的时间复杂度和插入结点一样，也是O(n)。链表上实现的插入和删除运算，无须移动结点，仅需修改指针。

延伸阅读

此文章所在专题列表如下：

1. 结构之美：定义一个线性表
2. 结构之美：线性表的查找、插入与删除操作
3. 结构之美：线性表的链式存储结构——链表
4. 结构之美：单链表的初始化、创建与遍历
5. 结构之美：单链表的头结点与头指针
6. 结构之美：使用头插法创建单链表
7. 结构之美：使用尾插法创建单链表
8. 结构之美：单链表的销毁删除
9. 结构之美：查找单链表指定位置结点的数据
10. 结构之美：在单链表指定位置插入数据
11. 结构之美：删除单链表指定位置的数据
12. 结构之美：单链表逆序
13. 结构之美：判断单链表中是否有环
14. 结构之美：获取单链表倒数第N个结点值
15. 单循环链表的初始化、创建、删除、查找与遍历
16. 结构之美：双向循环链表的结构与定义

本文地址：http://www.nowamagic.net/librarys/veda/detail/1823，欢迎访问原出处。