#pragma once
#include<stdio.h>
#include<string.h>
#include<assert.h>
#include <stdlib.h>
typedef int DataType;
//定义一个结构体类型
typedef struct LinkNode
{
DataType data;//定义节点的数据
struct LinkNode *next;//保存下一个类型节点的地址
}LinkNode, *pLinkNode, *pList;//指向节点的指针
void InitLinkList(pList* pHead);
void Destroy(pList *pHead);
void PushBack(pList* pHead, DataType x);
void PopBack(pList* pHead);
void PushFront(pList* pHead, DataType x);
void PopFront(pList* pHead);
void PrintList(pList list);
int GetListLength(pList head);
pLinkNode Find(pList head, DataType x);
void Insert(pList *pHead, pLinkNode pos, DataType x);
void Remove(pList *pHead, DataType x);
void RemoveAll(pList *pHead, DataType x);
void Erase(pList *pHead, pLinkNode pos);
void ReverseList(pList *pHead);
void EraseNotTail(pLinkNode pos);
//1 pHead是单链表的头指针，它指向表中第一个节点，若phead==null表示单链表是一个空表
void InitLinkList(pList* pHead)//pHead是单链表的头指针，它指向表中第一个节点，若phead==null表示单链表是一个空表
{
assert(pHead);
(*pHead)->next=NULL;
}
//2 由于在后边的 几个函数中都需要创建一个新的节点，所以将创建这个节点的过程直接分装成一个函数，使得程序简洁明了
pLinkNode BuyNode(DataType x)
{
pLinkNode newNode=(pLinkNode)malloc(sizeof(LinkNode));
//创建一个新节点
    newNode->data=x;
newNode->next=NULL;
return newNode;
}
//3 尾插法建立单链表，首先判断当前链表是否为空，若为空
//  则直接插入节点，否则逐次遍历，将最后一个节点的指针域赋值要插入的节点
void PushBack(pList* pHead, DataType x)
{
assert(*pHead);
pLinkNode cur=*pHead;
pLinkNode newNode=BuyNode(x);
   //尾部插入
if(cur==NULL)
{
  cur=newNode;
  return;
}
else
{	
while(cur->next)//有节点
{
  cur=cur->next;
}
cur->next=newNode;
}
}
//3尾删方法删除单链表，首先判断，
//（1）若当前链表为空则不用删除直接返回
//（2）若链表只有一个节点(*pHead)->next==NULL，则释放*pHead，即可达到删除下一个节点的效果
//（3）若链表含有两个或两个以上的节点，则逐个遍历,当出现当前遍历的节点cur->next->next为空的时候通过free(cur->next)即可删除最后一个节点
void PopBack(pList* pHead)//尾删法
{  
pLinkNode cur=*pHead;
   assert(pHead);
   //没有节点
   if(cur==NULL)
   {
   return;
   }
   //有一个节点
   else if(cur->next==NULL)
   {
   free(cur);
   cur=NULL;
   
   }
   //有两个或者两个以上的节点
   else
   {
   while(cur->next->next)
   {
   cur=cur->next;
   }
   free(cur->next);
   cur->next=NULL;
   }
}
//4 头插法建立单链表调用之前的BuyNode函数建立一个新的节点
//若当前链表为空则直接插入，否则将newNode->next=*pHead，再将*pHead=newNode
void PushFront(pList* pHead, DataType x)//头插法
{
pLinkNode newNode=BuyNode(x);
assert(pHead);
if(*pHead==NULL)
{
*pHead=newNode;
return;
}
else
{
      newNode->next=*pHead;
      *pHead=newNode;
}
}
//5 头删法删除单链表的节点
//（1）若单链表为空，则直接返回
/*（2）否则保存要删除的首节点，然后*pHead=(*pHead)->next；将要删除的节点释放即可*/
void PopFront(pList* pHead)//头删法
{   pLinkNode del;
assert(pHead);
if(*pHead==NULL)
{
return;
}
else
{
pLinkNode del=*pHead;//首先保存要删除的节点
*pHead=(*pHead)->next;
free(del);
    del=NULL;
}
}
//6 打印单链表
void PrintList(pList list)//打印单链表
{
while(list)
{
printf("%d->",list->data);
list=list->next;
}
printf("over");
}
//7 由于链表是在堆上动态开辟的存储空间，所以使用完之后必须销毁
//如果当前链表为空，则直接返回，反之开始判断当前节点是否为空，
//如果不为空，则保存并且释放掉，逐次向后遍历，即可达到销毁的目的
void Destroy(pList *pHead)
{
 pLinkNode cur=*pHead;
 assert(pHead);
 if(*pHead==NULL)
 {
   return;
 }
 else
 {
 while(cur)
 {
  pLinkNode del=cur;
  cur=cur->next;
  free(del);
  del=NULL;
 }
 
 }
}
//8 计算链表的长度
//设计一个计数器，一次遍历，只要当前节点不为空，给计数器自增即可
int GetListLength(pList head)
{
int count=0;
pLinkNode cur=head;
while(cur)
{
count++;
   cur=cur->next;
}
   return count;
}
//9 寻找链表中数据
//（1）首先判断如果当前链表为空，则查找失败直接返回
//（2）若当前节点不为空，则判断当前节点的数据域的值是否和要查找的数据相等，
//若相等则返回当前节点，否则逐次向后遍历，直到最后 任然没有找到则返回空即可
pLinkNode Find(pList head, DataType x)
{
pLinkNode cur=head;
if(cur==NULL)
{
return;
}
else
{
while(cur)
       if(cur->data==x)
   {
   return cur;
   }
   else
   cur=cur->next;
}
return NULL;
}
//10 在指定位置插入一个节点
//（1）断言要插入的位置是否合法
  /*（2）调用函数创建节点pLinkNode newNode=BuyNode(x)；
（3）依次遍历当前节点和要插入的位置相等时newNode->next=cur->next，然后cur->next=newNode*/
void Insert(pList *pHead, pLinkNode pos, DataType x)
{
assert(pHead);
assert(pos);
pLinkNode newNode=BuyNode(x);
pLinkNode cur=*pHead;
while(cur!=pos)
{
cur=cur->next;
}
newNode->next=cur->next;
cur->next=newNode;
}
//11 删除链表中某个指定位置的节点
//（1）若当前链表为空则直接返回
//（2）判断当前节点是否为空，若不为空则判断是否和要删除的节点只相等
//（3）若相等，则判断是否为头节点，然后在删除
//（4）若相等且不为头节点，则有
void Remove(pList *pHead, DataType x)
{  
pLinkNode cur=*pHead;
pLinkNode del=NULL;
pLinkNode prev=NULL;
assert(pHead);
if(pHead==NULL)
{
return;
}
else
{
while(cur)
{
if(cur->data==x)
{
del=cur;
if(cur==*pHead)
{
*pHead=(*pHead)->next;
}
else
{
prev->next=cur->next;
}
free(del);
break;  //循环不能一味的执行下去，因为只删除一次
}
prev=cur;
cur=cur->next;
}
     }
}
void RemoveAll(pList *pHead, DataType x)
{  
pLinkNode cur=*pHead;
pLinkNode del=NULL;
pLinkNode prev=NULL;
assert(pHead);
if(pHead==NULL)
{
return;
}
else
{
while(cur)
{
if(cur->data==x)
{
del=cur;
if(cur==*pHead)
{
*pHead=(*pHead)->next;
cur=*pHead;
}
else
{
prev->next=cur->next;
cur=prev->next;
}
free(del);
}
else
{
prev=cur;
cur=cur->next;
}
}
     }
}
//链表常见的面试题
//1 删除非尾节点（删除无头单链表的非尾节点）
//（1）将当前节点和下一个节点的数据域交换，然后在删除下一个节点即可
void EraseNotTail(pLinkNode pos)
{
pLinkNode del=pos->next;//将要删除的节点保存起来，删除当前节点的下一个节点
pos->data=pos->next->data; /*交换当前即诶单和下一个节点的数据域*/
pos->next=del->next;
free(del);
del=NULL;
}
//2 反转链表  
//头插问题，每次取下一个节点依次头插，将第一个节点的指针域赋值为空，然后取下一个节点进行头插
void ReverseList(pList *pHead)
{
pLinkNode pnewHead=NULL;/*一注意赋空值定*/
pLinkNode cur=*pHead;
pLinkNode prev=NULL;
if(cur==NULL)
{
return;
}
if(cur->next==NULL)
{
return;
}
   while(cur)
   {
   prev=cur;
   cur=cur->next;
   prev->next=pnewHead;
   }
   *pHead=pnewHead;
}
//3 排序链表  （冒泡排序）
void Bubblesort(pList *pHead)
{
pLinkNode end=NULL;
pLinkNode cur=*pHead;
assert(pHead);
while(cur!=end)
{
while(cur&&(cur->next!=end))
{
if(cur->data>cur->next->data)
{
DataType tmp=cur->data;
cur->data=cur->next->data;
cur->next->data=tmp;
}
cur=cur->next;
}
end=cur;
cur=*pHead;
}
}
//4  在当前节点前插入一个数据
//首先在pos后插入一个数据，然后将pos和它后边的数据进行交换，完了删除后边的节点即可
void InsertFrontNode(pLinkNode pos,DataType x)
{
pLinkNode newNode=BuyNode(x);
assert(pos);//防止在空值后边插入一个数据
newNode->next=pos->next;
pos->next=newNode;
DataType tmp=pos->data;
pos->data=pos->next->data;
pos->next->data=tmp;
}
//5合并两个有序链表
pLinkNode Merge(pList l1,pList l2)
{
pLinkNode cur=NULL;
pList newHead=NULL;
if(l1==l2)
{
return l1;
}
if((l1==NULL)&&(l2!=NULL))
{
return l2;
}
if((l1!=NULL)&&(l2==NULL))
{
return l1;
}
if(l1->data<l2->data)//首先确定头结点
{
newHead=l1;
l1=l1->next;
}
else
{
newHead=l2;
l2=l2->next;
}
while(l1&&l2)
{
if(l1->data<l2->data)
{
cur->next=l1->next;
l1=l1->next;
}
else
{
cur->next=l1;
l2=l2->next;
}
cur=cur->next;
}
if(l1)
{  
cur->next=l1;
}
else
{
    cur->next=l2;
}
return newHead;
}
//其实有几道面试题没来得及整理呢
测试部分代码：
#define _CRT_SECURT_N0_WARNINGS 1
#include<stdio.h>
#include"linklist.h"
void Test1()
{
pList mylist;
InitLinkList(&mylist);
PushFront(&mylist,1);
PushFront(&mylist,2);
PushFront(&mylist,3);
PushFront(&mylist,4);
PrintList(mylist);
}
void Test2()
{
pList mylist;
InitLinkList(&mylist);
PushFront(&mylist,1);
PushFront(&mylist,2);
PushFront(&mylist,3);
PushFront(&mylist,4);
PrintList(mylist);
 
EraseNotTail(2);
PrintList(mylist);
}
void Test3()
{
pList l1;
InitLinkList(&l1);
PushFront(&l1,1);
PushFront(&l1,3);
PushFront(&l1,5);
PushFront(&l1,7);
PrintList(l1);
pList l2;
InitLinkList(&l2);
PushFront(&l2,2);
PushFront(&l2,4);
PushFront(&l2,6);
PushFront(&l2,8);
PrintList(l2);
pList l;
l=Merge(l1,l2);
PrintList(l);
}
int main()
{
void Test2();
system("pause");
}