指针引用在链表删除中的应用

问题引发

在做链表删除某一特定值元素时发现一些小小的问题，因为之前写链表都是传指针没有传过指针的引用，在写408 P.40第一题时，发现可以做到删除某一特定值，但对于如下的情况会出现野指针：

在需要删除尾结点时会生成野指针，原码如下：

void P40_1(LinkList L, int x)
{
	if (L == NULL)return;
	if (L->data == x )
	{
		if (L->next != NULL)//删除中间结点
		{
			LNode* p = L->next;//NULL不可以指向下一个位置
			L->next = p->next;
			L->data = p->data;
			free(p);
		}
		else//删除尾结点
		{
			LNode* p = L;
			L = L->next;
            //这里L虽然指向了后一个空，但因为传的是指针地址，没有引用那样做到对原链表清除地址 
			L = NULL;//-----1
			free(p);
		}
	}
	else 
    {
		//如果加引用，在检测到L下不是x时会让后面结点替代L，因为是对原链表操作
        L = L->next;//-----2
	}
    P40_1(L, x);//删除元素后当前位置会赋值后一个元素值，所以向下一个位置会错过，这里继续向L递归
}

野指针

首先回忆一下野指针，也可以是我们熟悉的浅拷贝问题，即两个指针指向同一块区域，但没有申请额外的空间，任一指针去修改都会改变空间里的值，一旦对某个指针进行free操作，另一个指针就会成为野指针。

拿上面的代码为例，就是因为传入的仅仅是一个结点L，这个L是一个局部变量，只能包含其本身和后面的各个结点，如果在这时需要删除的L是一个尾指针的话，直接在1处free(L);L=NULL;两步是不能对原表的L’结点赋值NULL的，即原表L’指向的空间虽然被free了，但指向仍在，就会指向未知区域而造成野指针。

解决方法

为了解决这一问题，我使用了答案中的给指针加引用，但结果会发现整个链表被删差不多了，经过一波分析，发现是2处的L=L->next的问题，在加了引用之后，因为所有更改都相当于全局操作，即在原链表上进行操作，这里只要碰到不是x的情况就会让L后面的结点替代L，改进方法是不使用L=L->next表示下一个结点，而直接传L->next

void P40_1(LinkList &L, int x)
{
	if (L == NULL)return;
	if (L->data == x )
	{
		if (L->next != NULL)//删除中间结点
		{
			LNode* p = L->next;//NULL不可以指向下一个位置
			L->next = p->next;
			L->data = p->data;
			free(p);
		}
		else//删除尾结点
		{
			LNode* p = L;
			L = L->next;//这里L虽然指向了后一个空，但因为传的是指针地址，没有引用那样做到对原链表清楚地址
			L = NULL;
			free(p);
		}
		P40_1(L, x);
	}
	else {

		//L = L->next;//如果加引用，在检测到L下不是x时会让后面结点替代L，因为是对原链表操作
		P40_1(L->next, x);
	}
}

优化

对于一般不加引用的删除，由于每次只能操作局部变量L和后面的结点，所以常规方法需要操作三个结点，而且删除只能删除中间结点q，所以要加赋值，不然会断链(408-P.33)

q=L->next;

L->next=q->next;

L->data=q->data;//想要删的是L下的data，但必须要删中间结点q，不然会断链，所以这里用赋值的方法

free(p);

因为加了引用，所以可以直接对原链表操作不会断链，用后面结点替代当前节点L，即L=L->next，不需要再用3个结点进行删除

void A_P40_1(LinkList &L, int x)
{
	LNode* p;
	if (L == NULL)
		return;
	if (L->data == x)//删除中间结点操作三个结点太麻烦，所以合并
	{
		p = L;
		L = L->next;
		free(p);//p作为局部变量指向的空间被释放
		A_P40_1(L, x);
	}
	else
		A_P40_1(L->next, x);
}

带头结点的删除

如果带头结点呢，这里选用循环算法处理，这里加不加引用都可以，因为是对三个指针进行的操作，即删除的是中间结点（注意这里因为有头结点，可以做到生成一个前驱指针pre，所以不需要赋值了，而之前相当于需要删除的是三个里第一个结点，但删除只能删中间的，所以用了赋值）

void P40_2(LinkList L, int x)
{
	LNode* p = L->next,*pre=L,*q;
	while (p != NULL)
	{
		if (p->data == x)
		{
			q = p;
			p = p->next;
			pre->next = p;
			free(q);
		}
		else
		{
			pre = p;
			p = p->next;
		}
	}
}

那这里为什么不会出现尾结点野指针的问题呢，因为这里除了把当前这个局部变量p结点用后面的结点代替（p后移），还有一步pre->next = p，即有前驱结点的信息，保证了前面结点后一个结点指向了空。

而无头结点的赋值法因为局部变量只有当前结点和后面结点的信息，实际要删除的是当前结点而妥协用了赋值法，没有pre指针来连接前后就直接释放，当然会造成野指针。

循环方法删除不带头结点链表所有值为x的结点

如果你上面看明白了，那请思考一下这一题的解法，因为我们知道不带头结点是需要删除当前结点的，操作三结点只能用赋值法还会出现尾结点野指针的问题，所以采用递归可以利用引用或二级指针来解决这个问题，保证操作的是双结点还不断链。

事实上，我们可以利用引用或二级指针先删除最前面所有值为x的元素，直到让链表首个结点不再是x，然后重新定义局部变量让首个结点设为pre前驱，后一个才是需要删除的结点，这样又可以操作三结点而不断链，这里展示的是二级指针的写法。

void P40_2_2(LinkList* L, int x) {
	while ((*L)->data == x) {
		(*L) = (*L)->next;
	}
	LNode* p = (*L)->next, * pre = *L, * q;
	while (p != NULL)
	{
		if (p->data == x)
		{
			q = p;
			p = p->next;
			pre->next = p;
			free(q);
		}
		else
		{
			pre = p;
			p = p->next;
		}
	}
}

其它方法

还可以牺牲空间来实现，即重新构建一张链表，将不是x值的结点插入。