/*****************************************************/

/*假设有一个没有头指针的单链表。一个指针指向此单链表**/

/*中间的一个节点，请将该节点从单链表中删除************/

/*****************************************************/

#include <stdlib.h>

#include <stdio.h>

#include <assert.h>

typedef struct Node

{

char value;

struct Node *next;

}Node;

void DeleteRandomNode(Node * pCurrent);

int main()

{

Node *first = (Node *)malloc(sizeof(Node));

Node *second = (Node *)malloc(sizeof(Node));

Node *thrid = (Node *)malloc(sizeof(Node));

Node *fourth = (Node *)malloc(sizeof(Node));

/*Init*/

first->value = 'A';

first->next = second;

second->value = 'B';

second->next = thrid;

thrid->value = 'C';

thrid->next = fourth;

fourth->value = 'D';

fourth->next = NULL;

printf("%c->%c->%c->%c\n",first->value,second->value,thrid->value,fourth->value);

DeleteRandomNode(second);

printf("%c->%c->%c\n",first->value,second->value,fourth->value);

return 0;

}

void DeleteRandomNode(Node * pCurrent)

{

assert(pCurrent != NULL);

Node *pNext = pCurrent ->next;

if(pNext != NULL)

{

pCurrent ->next = pNext ->next;

pCurrent ->value = pNext ->value;

delete pNext;

}

}

 

因为无头单链表没有头指针，所以无法由头指针追溯到待删除节点的前一节点。

所以此处用了“狸猫换太子”的方法把节点删除了。

核心就在

pCurrent -> Next = pNext -> Next;

pCurrent -> Data = pNext -> Data;

delete pNext;

 

这个实现没有创建单链表，只是直接创建了四个相连的节点。模拟出了无头单链表中节点的删除。

注意要为指向结构体的指针分配内存空间，要不运行时会报错。

在函数调用里面申请的内存也要delete掉。