删除单链表链表中所有结点元素值为x的结点_带头节点的单链表删除值为x的节点

1、删除不带头结点的单链表中所有值为x的结点——采用偷梁换柱法，这种方法不用考虑待删除结点的直接前驱是谁，例如若我们想要删除p结点，可采用以下方法：

                        LNode* t=p;   //t指向待删除结点

                        p=p->next;     //要删除p，那么我们就将p换成p的后继节点即可，然后将原来的p回收

                        free(t);

代码实现：

//删除不带头结点的链表中所有值为x的结点，采用递归的思想
void DeleteX(LinkList& L, int x)
{
	if (L == NULL)
		return;
	if (L->data == x)
	{
		LNode* t = L;
		L = L->next;
		free(t);
		DeleteX(L, x);
	}
	else
	{
		DeleteX(L->next, x);
	}
	return;
}

2、删除带头结点的单链表中所有值为x的结点，对于带头结点的单链表我们从头结点开始遍历链表时我们始终判定的是当前结点L的直接后继的元素值是否为x，若是，那么当删除L的直接后继的时候，L的直接后继的直接前驱就是L本身，而知道一个单链表中某个结点的直接前驱是删除这个结点的关键，所以删除L的直接后继是很简单的操作，从这里也可以体会到为什么单链表中增加一个头结点可以方便运算的实现了，对于不带头结点的单链表删除值为x的结点就不可以采用这种方法

代码实现

 
//删除带头结点的链表中所有值为x的结点，采用递归的思想
void DeleteHeadX(LinkList& L, int x)
{
	if (L->next == NULL)
		return;
 
	if (L->next->data == x)
	{
		//用这种方法的好处是我们判定的是L的直接后继的元素值是否为x，若是，那么当删除L的直接后继的时候L的直接后继的直接前驱就是L本身，
		//知道一个单链表中某个结点的直接前驱是删除这个结点的关键，因为单链表的节点中只存放了指向直接后继的指针，
		//而删除某个单链表中的结点时既需要知道这个结点的直接前驱也需要知道这个结点的直接后继
		LNode* t = L->next;
		L->next = t->next;
		free(t);
		DeleteHeadX(L, x);
	}
	else
	{
		DeleteHeadX(L->next, x);
	}
	return;
}

以上代码读者可以自己定义带头结点和不带头结点的单链表来测试一下，我自己测试是正确的