建立一个带附加头结点的单链表.实现测长/打印/删除结点/插入结点/逆置/查找中间节点/查找倒数第k个节点/判断是否有环

// 建立一个带附加头结点的单链表/测长/打印
#include<iostream>
using namespace std;

typedef struct node
{
 int data;
 node *next;
}LinkList;

LinkList *creat()
{
 LinkList *head,*p,*s;
 int x;
 head=new LinkList[sizeof(LinkList)];
 head->data=0;
 p=head;
 while(1)
 {
  cout<<"Please input the data:"<<endl;
  cin>>x;
  
  if(x==0) break;
  
  s=new LinkList[sizeof(LinkList)];
  s->data=x;
  p->next=s;
  p=s;
 }
    p->next=NULL;
 return head;
}

int length(LinkList *head)
{
 int n=0;
 LinkList *p;
 p=head->next;
 while(p!=NULL)
 {
  p=p->next;
  n++;
 }
 return n;
}

void print(LinkList *head)
{
 LinkList*p;
    p=head->next;
 while(p!=NULL)
 {
  cout<<p->data<<" ";
  p=p->next;
 }
 cout<<endl;
}

/*LinkList *del(LinkList *head,int deldata)
{
 LinkList *p1,*p2;
 p1=head;
 while(deldata != p1->data && p1->next != NULL)
 {
  p2=p1;
  p1=p1->next;
 }
 if(deldata==p1->data)
 {
  if(p1==head)
  {
   head=p1->next;
   free(p1);
  }
  else
   p2->next=p1->next;
 }
 else
  cout<<deldata<<"could not been found"<<endl;
 return head;
}*/
LinkList *del(LinkList *head,int deldata)
{
 LinkList *p1,*p2;
 p1=head;
 while(p1->next !=NULL)
 {
  p2=p1;
  p1=p1->next;
  if(deldata==p1->data)
  {
   p2->next=p1->next;
   break;
  }
 }
 if(p1->next ==NULL)
  cout<<deldata<<" could not been found"<<endl;
 return head;
}

LinkList *insert(LinkList *head,int num)
{
 LinkList *p0,*p1,*p2;
 p1=head;
 p0=new LinkList[sizeof(LinkList)];
 p0->data=num;
 while(p1->next != NULL)
 {
  p2=p1;
  p1=p1->next;
  if(p0->data<p1->data)
  {
   p2->next=p0;
   p0->next=p1;
   break;
  }
  if(p0->data==p1->data)
  {
   cout<<"yao cha ru de yuan su yi jing cun zai"<<endl;
   break;
  }
 }
 if(p0->data>p1->data)
 {
  p1->next=p0;
  p0->next=NULL;
 }
 
 return head;
}

LinkList *Reverse(LinkList *head)
{
 LinkList *p1,*p2,*p3;
 if(head==NULL||head->next==NULL)
  return head;
 p1=head;
 p2=p1->next;
 p3=p2->next;
 p1->next=NULL;
 while(p3)
 {
  p2->next=p1;
  p1=p2;
  p2=p3;
  p3=p3->next;
 }
 p2->next=p1;
 head=p2;
 return head;

}

LinkList* searchmid(LinkList* head)
{
 LinkList* mid=new LinkList[sizeof(LinkList)];
 LinkList *p1=head->next;
 LinkList *p2=p1;

 while(p1->next != NULL && p1->next->next != NULL  )
 {
  p1=p1->next->next;
  p2=p2->next;
 
 }
 mid=p2;
 return mid;
}

LinkList* finddaoshuk(LinkList* head,int k)
{
 LinkList *p1=head->next;
 LinkList *p2=p1;
 for(int i=1;i<k;i++)
 {
  if(p1->next!=NULL)
   p1=p1->next;
  else return NULL;
 }
 while(p1->next!=NULL)
 {
  p1=p1->next;
  p2=p2->next;
 }
 return p2;
}

bool IsCircle(LinkList* head)
{
 LinkList *p1=head->next;
 LinkList *p2=p1;
 while(p1->next != NULL && p1->next->next != NULL  )
 {
  p1=p1->next->next;
  p2=p2->next;
  if(p2==p1) return true;
 }
 return false;
}

int main()
{
 LinkList*node=creat();
 //cout<<length(node)<<endl;
 print(node);
 bool IsCir=IsCircle(node);
 if(IsCir==true) cout<<"The list has circle"<<endl;
 else cout<<"The list has not circle"<<endl;

 /*LinkList* mid=searchmid(node);
 cout<<mid->data<<endl;
 cout<<"Please output dao shu di k ge jie dian"<<endl;
 int k=2;
    LinkList* pk=finddaoshuk(node,k);
 if(pk==NULL) cout<<k<<" k is biger than the lengh of node";
 else cout<<pk->data<<endl;*/

/* LinkList*afterdel=del(node,3);
 print(afterdel);
 LinkList*afterinsert=insert(node,10);
 print(afterinsert);

 cout<<"after reverse LinkList"<<endl;
 LinkList*afterreverse=Reverse(afterinsert);
 print(afterreverse);*/

 return 0;
}