删除链表中的节点

 

链表：

typedef int DataType;
typedef struct Node
{
	DataType data;
	struct Node* next;
}Node, *pNode, List, *pList;

 

            我们知道在链表中删除一个节点，最原始的方法就是讲整个链表遍历一遍，遇到需要删除的就将它删除就可以，但是遍历一遍链表，其时间复杂度为O(n)，但是题目中要求在O(1)时间内删除链表节点，我们的做法是：将需要删除节点的下一个节点的内容复制到需要删除的节点，然后删除需要删除节点的下一个节点，这样就相当于将需要删除节点删除。如图：

      但是这样的做法也有问题，如果需要删除的节点是最后一个节点，那么它不存在下一个节点，怎么办？我们任然从链表头开始遍历，遍历到最有一个节点前的节点，然后进行删除操作就可以了。

         最后当链表中只有一个节点，既是头结点，也是尾节点，我们进行删除操作之后，需要将头指针指向NULL;

 

 

参考代码：

void DeleteNode(pList* pplist, pList pos)
{
	pList cur = NULL;
	assert(pplist != NULL);
	if (*pplist == NULL||pos==NULL)
		return;
	//要删除的节点不是尾节点
	if (pos->next != NULL)
	{
		cur = pos->next;
		cur->data = pos->data;
		pos->next = cur->next;

		free(cur);
		cur = NULL;
	}
	//只有一个节点（既是头，又是尾）
	else if (*pplist == pos)
	{
		free(pos);
		pos = NULL;
		*pplist = NULL;
	}
	//有多个节点，删除尾节点
	else
	{
		pList cur = *pplist;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		cur->next = NULL;

		free(pos);
		pos = NULL;
	}
}

 

 

       我们从头开始遍历链表，如果一个节点的内容和下一个节点的内容一样，我们就认为这两个节点是重复节点，这样的所有节点都要被删除，在删除后，为了让链表连在一起，我们需要确保将每次删除后将这个节点的前一个节点指向下一个不是重复节点的节点。

         如上图：我们从头开始遍历，当遍历到3的时候，让（pre）指针指向2，3和4重复，我们删除这四个节点，最后将（pre）指向5。

参考代码： 

void DeleteSameNode(pList* pplist)
{
	pList cur = *pplist;
	pList pre = NULL;
	pList Next = NULL;
	assert(*pplist != NULL);
	if (*pplist == NULL)
		return;
	while (cur != NULL)
	{
		Next = cur->next;
		int needDelete = 0;
		if (Next != NULL&&cur->data == Next->data)
			needDelete = 1;
		if (needDelete == 0)//不是重复节点，往下遍历
		{
			pre = cur;
			cur = cur->next;
		}
		else
		{
			int data = cur->data;
			pList del = cur;
			while (del->data == data&&del != NULL)//是重复节点，删除往后的所有的重复的节点
			{
				Next = del->next;
				free(del);
				del = NULL;
				del = Next;
			}
			if (pre == NULL)//第一个节点就是重复节点
			{
				*pplist = Next;
			}
			else
				pre->next = Next;//pre指向下一个不是重复节点的节点
		}
		cur = Next;
	}
}