資料結構——算法之（027）（ 在O(1)時間内删除連結清單結點）

【申明：本文僅限于自我歸納總結和互相交流，有纰漏還望各位指出。 聯系郵箱：[email protected]】

題目：在O(1)時間内删除連結清單結點，且不知道連結清單頭

題目分析：

1、把要删除節點的下一個節點的資料拷貝到要删除的節點

2、把下一個節點删除

算法實作：

#include <stdio.h>
#include <stdlib.h>

typedef struct _list_node
{
	int        key;
	struct _list_node  *next;
}list_node;

void *list_insert(list_node *head, int key)
{
	list_node *p = head;
	while(p->next != NULL)
		p = p->next;
	list_node *node = calloc(1, sizeof(list_node));
	node->key = key;
	node->next = NULL;

	p->next = node;
}

void list_delete(list_node *del_node)
{
	list_node *p = del_node->next;
	del_node->key = p->key; /*copy data*/
	del_node->next = p->next;
	free(p);
}

void list_dispaly(list_node *head)
{
	list_node *p = head->next;
	printf("list:");
	while(p)
	{
		printf(" %d", p->key);
		p = p->next;
	}
	printf("\n");
}

int main(int argc, char *argv[])
{
	list_node *head = calloc(1, sizeof(list_node));
	head->key = 0;
	head->next = NULL;

	list_insert(head, 1);	
	list_insert(head, 2);	
	list_insert(head, 3);	
	list_insert(head, 4);	
	list_insert(head, 5);

	list_dispaly(head);	
	list_delete(head->next->next);
	list_dispaly(head);	
	return 0;
}