数据结构【链表01】----删除单链表中所有值为x的节点_带头结点的单链表删除所有值为x

问题描述：
在带头结点的单链表L中，删除所有值为x的节点，并释放其内存空间，假设值为x的节点不唯一，试编写算法实现上述代码。

问题分析
**（方法一）**使用pre指针指向头节点，用pre->next逐个扫描，如果pre->next节点的值为x，pre指针指向pre->next->next，删除pre->next指针，然后释放pre->next这个节点。如果pre->next的值不为x则pre往后移动一个节点
为了简化算法，可以引用p指针表示pre节点的后继指针，为了释放p指针的内存，另外引用一个q指针。
**（方法二）**使用尾插法重新创建一个链表，把原来的L链表的节点重新接到L上去，如果节点的值为x则不接了。

代码实现

//在不带头节点的单链表L中，删除所有值为X的节点，并释放其内存空间
void delete_x(LinkList &L,Elemtype x){
	LNode *p = L->next,*pre = L,*q;		//p指针指向挨个扫描的指针，pre指针指向p指针前一个节点 
	while(p != NULL){
		if (p->data == x){
			q = p;				//q指向该节点，待会释放了 
			pre->next = p->next;	//删除该节点 
			p = p->next;
			free(q)				//释放节点 
		}
		else{
			pre = p;			//如果不想当，p节点和pre节点往后移动 
			p = p->next;
		}
	}
} 

void delete_x_header(LinkList &L,Elemtype x) {
	LNode *p = L->next,*q;
	while(p != NULL){
		if(p->data != x){
			L->next = p;
			L = p;
			p = p->next
		}
		else{
			q = p;
			p = p->next;
			free(q);
		}
	}
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

时间复杂度：O（n）
空间复杂度：O（1）