单链表操作大全
tinyfisher 发表于 2012-07-22
单链表的操作一般包括：建立，删除节点，插入节点，链表反转
1.单链表建立，包括从终端输入和由数组转换而来两种：
typedef struct node
{
int num;
struct node * next;
}Node,*pNode;
pNode CreateLink()
{
pNode head=(pNode)malloc(sizeof(Node));
pNode p=head;
int a;
printf("please input:\n");
scanf("%d",&a);
while(a!=-1)
{
pNode q=(pNode)malloc(sizeof(Node));
q->num=a;
p->next=q;
p=q;
scanf("%d",&a);
}
p->next=NULL;
head=head->next;
return head;
}
pNode CreateLinkFromArray(int a[],int len)
{
pNode head=(pNode)malloc(sizeof(Node));
pNode p=head;
int i=0;
while(i<len)
{
pNode q=(pNode)malloc(sizeof(Node));
q->num=a[i];
p->next=q;
p=q;
i++;
}
p->next=NULL;
head=head->next;
return head;
}
2.单链表删除节点，考虑删除头结点，尾节点和中间节点：
pNode del(pNode head,int key)
{
pNode p=head;
pNode q=head;
if(p==NULL) //若链表为空
{
return NULL;
}
if(p->num==key) //删除头指针
{
head=head->next;
free(p); // 释放删除节点空间
return head;
}
while(p->num!=key&&p->next!=NULL) //遍历链表直到最后一个元素 寻找key，若有删掉
{
q=p;
p=p->next;
}
if(p->next==NULL&&p->num==key) //删除尾元素
{
q->next=NULL;
free(p);
}
else if(p->next!=NULL) //删除中间元素
{
q->next=p->next;
free(p);
}
else
{
printf("not found\n");
}
return head;
}
3.单链表插入元素，考虑插入头结点，尾节点和中间节点
pNode insert(pNode head,int value)
{
pNode s=(pNode)malloc(sizeof(Node));
s->num=value;
pNode p=head;
pNode q=head;
if(head==NULL) //链表为空
{
s->next=NULL;
return s;
}
while(p->num<value&&p->next!=NULL)
{
q=p;
p=p->next;
}
if(p->next==NULL&&p->num<value) //插入尾节点
{
p->next=s;
s->next=NULL;
return head;
}
else if(p==head) //插入头结点
{
p=s;
s->next=q;
return p;
}
else
{
q->next=s;
s->next=p;
return head;
}
}
4.单链表反转
pNode reverse(pNode head)
{
if(head==NULL)
{
return NULL;
}
if(head->next==NULL)
{
return head;
}
pNode p1,p2,p3;
p1=head;
p2=head;
while(p2->next!=NULL)
{
p3=p2->next;
p2->next=p1;
p1=p2;
p2=p3;
}
p2->next=p1;
head->next=NULL;
head=p2;
return head;
}