数据结构：C语言实现----带头结点的单链表

带头结点的单链表

特点：
①头结点定义在栈区，不保存数据，起标记作用，不参与具体运算。
②其他数据结点在堆区，动态申请内存/

带头结点的单链表结构体声明

typedef struct Node
{
 int data;
 struct Node *next;
}Node, *LinkList;

具体实现如下：

（1）初始化：头结点本身已存在，只需将头的next置为NULL

void InitLinkList(LinkList plist)
{
 assert(plist != NULL);
 if(plist == NULL)
 {
  return;
 }
 plist->next = NULL;
}

（2）求链表长度

int Listlength(LinkList plist)
{
 assert(plist != NULL);
 if(plist == NULL)
 {
  return -1;
 }
 
 plist->data=0;
 LinkList p = plist->next;
 while(p!=NULL)
 {
	plist->data++;
 	p=p->next;
 } 
 return plist->data;
 }

(3)求结点位置，返回该结点

LinkList GetNode(LinkList plist, int pos)
{
 assert(plist != NULL);
 if(plist == NULL)
 {
  return NULL;
 }

 if(pos<0) //判断pos是否合法
 {
  return NULL;
 }

 LinkList p=plist;
 while(pos!=0 && p!=NULL)
 {
  p=p->next;
  pos--;
 }
 return p;
}

（4）静态函数：申请新节点（避免了调用函数是进栈出栈，速度快很多）

static LinkList NodeApply(LinkList next, int val) 
{
 LinkList q=(Node *)malloc(sizeof(Node))；
 assert(q != NULL);
 if(q == NULL)
 {
  return NULL;
 }
 
 q->data=val;
 q->next = next; //先连后面
 
 return q;
}

（5）插入

void Insert(LinkList plist,int pos,int val)
{
 assert(plist != NULL);
 if(plist == NULL)
 {
  return;
 }

 LinkList p=GetNode(plist,pos); //找到要插入其后的结点的位置
 p->next=NodeApply(p->next,val);
}

（6）头插 //调用Insert

void InsertHead(LinkList plist, int val)
{
 assert(plist != NULL);
 if(plist == NULL)
 {
  return;
 }
 Insert(plist, 0, val);
}

（7）尾插

void InsertTail(LinkList plist, int val)
{
 assert(plist != NULL);
 if(plist == NULL)
 {
  return;
 }
 Insert(plist, Listlength(plist), val);
}

（8）输出

void Show(LinkList plist)
{
 assert(plist != NULL);
 if(plist == NULL)
 {
  return;
 }
 
 for(Node *p=plist->next; p!=NULL; p=p->next)
 {
  printf("%d -->",p->data);
 }
 
 printf("NULL\n");
}

（9）删除

void Delete(LinkList plist, int pos)
{
 assert(plist != NULL);
 if(plist == NULL)
 {
  return;
 }
 
  if(pos<0 || pos>Listlength(plist))
 {
  return;
 }

 LinkList p=GetNode(plist,pos-1); //要删除的结点的前一个结点；
 LinkList q=p->next; //要删除的结点
 p->next=q->next;
 free(q);
}

（10）O(1)头删

void DeleteHead(LinkList plist)
{
 assert(plist != NULL);
 if(plist == NULL)
 {
  return;
 }
 
 LinkList p= plist->next;
 if(p!=NULL)
 {
  plist->next=p->next; //删除p
 }
 free(p);
}

（11）尾删

void DeleteTail(LinkList plist)
{
 assert(plist != NULL);
 if(plist == NULL)
 {
  return;
 }
 Delete(plist,Listlength(plist));
}

（12）判空

int ListEmpty(LinkList plist)
{
 assert(plist != NULL);
 if(plist == NULL)
 {
  return -1;
 }
 
 if(plist->next == NULL)
 {
  return -1; //为空
 }
 
 return 0;
 }

(13)清空链表

void ClearList(LinkList plist)
{
 assert(plist != NULL);
 if(plist == NULL)
 {
  return;
 }
 
  while(!ListEmpty(plist)) //只要不为空
 {
  DeleteHead(plist); //进行头删，效率高
 }
}

链表习题

1.判断两个单链表是否相交

bool Union(LinkList listA,LinkList listB)
{
 assert(listA != NULL && listB != NULL);
 if(listA == NULL || listB == NULL)
 {
  return false;
 }
 
 int len1=Listlength(listA);
 int len2=Listlength(listB);
 LinkList p1=listA;
 LinkList p2=listB;
  if(len1>len2)
 {
  for(int i=0; i<len1-len2; i++)
  {
   p1=p1->next; //p1前进两条链表长度相差的长度单位，即p2在同一出发点
  }
 }
 else
 {
  for(int i=0; i<len2-len1; i++)
  {
   p2=p2->next;
  }
 }
  while(p1 != NULL)
 {
  p1=p1->next; //p1和p2同时后移
  p2=p2->next;
    if(p1 == p2) //相等即证明相交
   return p2;
 }
 return NULL;
 }

2.找倒数第K个结点

LinkList BackFind(LinkList plist,int k)
{
 assert(plist != NULL);
 if(plist == NULL)
 {
  return NULL;
 }

 LinkList p=plist;
 LinkList q=plist;
 for(int i=0; i<k && p != NULL; i++)
 {
  p=p->next; //即p先走k步
 }
 
  if(p == NULL) //k的值大于链表长度
  	return NULL;
  	
  while(p != NULL) //p和q同时向后走，则p走到最后时，q指向的就是倒数第k个
 {
  p=p->next;
  q=q->next;
 }
 
return q;
}

3.O(1)删除p节点(p是指向链表中的某一个不为尾节点的节点)

void DeleteO1(LinkList plist,LinkList delnode)
{
 assert(plist != NULL && delnode!=NULL);
 if(plist == NULL || delnode == NULL)
 {
  	return;
 }
  if(delnode->next == NULL) //若为尾结点，则调用尾删
 {
 	 DeleteTail(plist);
 }
  if(plist->next!=NULL) 
  {
  	LinkList tmp=delnode->next; //将要删除结点的后一个结点前移，即赋值给要删除的结点
  	delnode->data=tmp->data;
  	delnode->next=tmp->next;
  	free(tmp);
  }
 }

4.判断单链表是否有环

LinkList Circle(LinkList plist) 
{
 assert(plist != NULL);
 if(plist == NULL)
 {
  return NULL;
 }
 
 LinkList p1=plist; //慢指针
 LinkList p2=plist; //快指针
 
 while(p2!=NULL && p2->next!=NULL) //即类似跑步快的人，一定能追上跑步慢的人
 {
  	p1=p1->next;
  	p2=p2->next->next;
  	if(p1 == p2) 
     		return p1; //相交的第一个节点
 }

return NULL;
}

5.如果有环，找到入环的第一个节点

p(快):x+y+(k+y)*n
q(慢):x+y
推到可得：
2(x+y)=x+y+(k+y)*n
x=(k+y)(n-1)+k
k+y是一圈，n-1可认为m,即跑了m圈。x就等于k加上m个圈

LinkList FindLoop(LinkList plist)
{
 LinkList s=Circle(plist);
 if(s == NULL)
  return NULL;
  
 LinkList p=plist;
 LinkList q=s; //相交结点
 
  while(p != q)
 {
  p=p->next; //走x的路程 
  q=q->next; //把剩下的k走完，若是找不到入环，则一直转圈，直到找到入环点
 }
 return p;
}

6.实现链表逆置

void Reverse(LinkList plist)
{
 assert(plist != NULL);
 if(plist == NULL)
 {
  return;
 }
 
 LinkList p=NULL; //记录当前要处理的节点位置
 LinkList q=plist->next; //当前要处理结点的后一个结点
 LinkList s=q->next;
 
 while(q)
 {
  	q->next=p;
 	p=q;
        q=s;
  	if(s != NULL)         //q指向最后一个，s为空
  		s=s->next;
 }
  plist->next=p; //头指针指向最后一个
  }