链表逆置

#include<stdio.h>
#include<malloc.h>
//#include <iostream>
typedef int datatype;
typedef struct link
{datatype data;struct link *next;
}listnode;
typedef listnode * linklist;listnode *InitList()
{linklist head;if((head=(listnode *)malloc(sizeof(listnode)))==NULL)exit (-1);head->next=NULL;return head;
}void create(linklist head)/*用头插法或尾插法建立单链表*/
{//尾插法linklist p,q;q=head;datatype x;printf("请输入一个单链表以-1结束\n");scanf("%d",&x);while(x!=-1){p=(linklist)malloc(sizeof(listnode));p->data=x;q->next=p;q=p;scanf("%d",&x);}q->next=NULL;//头插法
/*   linklist p;head->next=NULL;datatype x;scanf("%d",&x);printf("请输入一个单链表以-1结束\n");while(x!=-1){p=(linklist)malloc(sizeof(listnode));p->data=x;p->next=head->nexthead->next=p;scanf("%d",&x);}
*/
}
void print(listnode *h)/*输出单链表*/
{listnode *p=h->next;if(p==NULL)printf("空表");while(p!=NULL)/*通过循环输出单链表*/{printf("%d   ",p->data);p=p->next;}printf("\n");getchar();
}void invert(linklist h)/*逆置单链表函数*/
{linklist p,q;p=h->next;h->next=NULL;while(p){q=p;p=p->next;q->next=h->next;h->next=q;}}int main()
{listnode *head;head=InitList();create(head);printf("输出一个单链表：\n");print(head);invert(head);printf("输出逆置后的单链表：\n");print(head);return 0;
}

> 2、合并两个链表

#include<stdio.h>
#include<malloc.h>
#include <iostream>
typedef int datatype;
typedef struct link
{datatype data;struct link *next;
}listnode;
typedef listnode* linklist;listnode *InitList()
{linklist head;if((head=(listnode *)malloc(sizeof(listnode)))==NULL)exit (-1);head->next=NULL;return head;
}void create(listnode *head)//创建一个带头结点的单链表
{linklist p,q;q=head;datatype x;printf("请输入一个单链表以-1结束\n");scanf("%d",&x);while(x!=-1){p=(linklist)malloc(sizeof(listnode));p->data=x;q->next=p;q=p;scanf("%d",&x);}q->next=NULL;}
void print(listnode *h)
{listnode *p=h;printf("输出一个单链表：\n");if(p->next==NULL)printf("空表");while(p->next){printf("%5d",p->next->data);p=p->next;}printf("\n");getchar();
}listnode *MergeList(listnode *la,listnode *lb,listnode *lc)//合并单链表
{linklist t;lc=la;t=lc;la=la->next;lb=lb->next;while(la&&lb){if(la->data<lb->data){t->next=la;t=t->next;la=la->next;}else{t->next=lb;t=t->next;lb=lb->next;}}if(la)t->next=la;if(lb)t->next=lb;return lc;}
int main()
{listnode *La,*Lb,*Lc;La=InitList();Lb=InitList();printf("建立一个单链表La\n");create(La);print(La);printf("建立一个单链表Lb\n");create(Lb);;print(Lb);Lc=MergeList(La,Lb,Lc);printf("输出合并后的单链表：");print(Lc);return 0;
}

> 3、约瑟夫环状问题

#include<stdio.h>
#include<malloc.h>
#include <iostream>
typedef struct  Node{int data;struct Node *next;}CListNode,*CLinkList;CLinkList create(int n)//创建一个不带头结点的循环单链表,采用尾插法
{CLinkList head,p,q;head=(CListNode*)malloc(sizeof(CListNode));printf("请输入一个循环链表:\n");scanf("%d",&head->data);head->next=head;q=head;while(--n){p=(CListNode*)malloc(sizeof(CListNode));scanf("%d",&p->data);p->next=q->next;q->next=p;q=p;}return head;
}
void print(CListNode *h)//输出循环单链表的内容
{CListNode *p=h;printf("输出一个单循环链表：\n");if(p==NULL)printf("空表");while(p->next!=h){printf("%5d",p->data);p=p->next;}printf("%5d",p->data);printf("\n");
}
void josephus(CLinkList head,int m){ CListNode *p,*q,*t;int i;p=head;i=0;while (p->next!=p)/*不是只有一个结点*/{while((i<m)&&(p->next!=p))/*查找第m个结点*/{q=p;p=p->next;i++;}if(p->next != p)/*不是最后一个结点，则删除*/{q->next=p->next;printf("%3d",p->data);free(p);p=q->next;i=1;}}printf("\n剩余%3d",p->data);printf("\n");
}int main(){int n;CLinkList head=NULL;//初始化头指针printf("请输入单循环链表结点的个数：");scanf("%d",&n);head=create(n);//建立循环单链表print(head);printf("所有元素的出列次序为：");josephus(head,3);return 0;
}