//天勤p32，查找链表（带头结点）中是否存在一个值为x的节点，若存在则删除该节点，并返回x，若不存在则返回0
//思路：其实就是个很简单的遍历问题，唯一的难点就是删除节点。
//删除节点步骤：另它的上一个节点指向它的下一个节点。然后释放该节点的空间
#include "stdio.h"
#include<stdlib.h>
typedef struct Node{ //结构体
int data;
Node *next;
}Node;
void init(Node *&p){ //初始化
p->next = NULL;
}
void listCreate(Node *&p,int n){ //参数：头节点，数据
Node *q = (Node *)malloc(sizeof(Node));
//****头插法建立（插入）链表*********(后进先出)
q->data = n;
q->next = p->next;
p->next = q;
//****************
}
void Traversal(Node *&p){ //遍历
Node *q = p->next;
while (q != NULL)
{
printf("%d ",q->data);
q = q->next;
}
}
//********核心函数****************************
int deleteSomeone(Node *&p,int x){
Node *q = p->next;
Node *w = p; //w作为q的前驱节点，方便删除
int n;
while (q != NULL){
if(q->data == x){
n = q->data;
w->next = q->next; //q前驱指向q后继，这样就相当于删除了q 节点
free(q); //释放空间，这样就彻底删除了q节点
return n;
}
q = q->next; //如果没有等的就往下找
w = w->next;
}
return 0; //如果能运行到这里说找不到。返回0
}
//********核心函数***********************
int main(){
Node *head = (Node *)malloc(sizeof(Node));
init(head);
for(int i=0;i<20;i++){
listCreate(head,i);
}
int x = 6;
int n = deleteSomeone(head,x);
Traversal(head);
printf(" ___________%d",n);
//printf("%d",head->data);
getchar();
return 0;
}