链表的7种操作

#include <iostream>using namespace std;struct node{	int data;	node *next;};node *create_list(){	node *head = NULL, *p = NULL, *s = NULL;	int len, val;	head = (node *)malloc(sizeof(node));	if (NULL == head)	{		cout << "分配内存失败，程序终止！" << endl;		exit(-1);//exit用于在程序运行的过程中随时结束程序,参数-1表示非正常退出	}	p = head;	p->next = NULL;	cout << "len=";	cin >> len;	for (int i = 0;i<len;++i)	{		cout << "输入第" << i + 1 << "个节点的值：";		cin >> val;		s = (node *)malloc(sizeof(node));		if (NULL == s)		{			cout << "分配内存失败，程序终止！" << endl;			exit(-1);		}		s->data = val;		p->next = s;//p指针起到连接节点的作用,s指针是生产指针		s->next = NULL;		p = s;	}	head = head->next;//指向首节点	p->next = NULL;	return head;}int list_length(node *head){	node *p = head;	int n = 0;	while (p != NULL)	{		p = p->next;		n++;	}	return n;}void PRint_list(node *head){	node *p = head;//p为遍历指针	while (NULL != p)	{		cout << p->data;		p = p->next;	}	cout << endl;	return;}node *reverse_list(node *head){	node *p1, *p2, *p3;	if (NULL == head || NULL == head->next)		return head;	p3 = head, p2 = p3->next;	while (p2)	{		p1 = p2->next;//p1先移向p2的下一个节点，先遣指针，以方便后面判断p2是否为NULL		p2->next = p3;//指针调转		p3 = p2;//p2,p3同时向前移动，p3最终返回逆序后链表的首节点的地址		p2 = p1;	}	head->next = NULL;	head = p3;//p1最终指向最后一个节点，也就是逆置之后的链表首节点	return head;}node *sort_list(node *head){	node *p = head;	int len = list_length(head);	int temp;	if (NULL == p || NULL == p->next)		return head;	for (int i = 0;i<len - 1;++i)	{		for (int j = 0;j<len - 1 - i;++j)		{			if (NULL != p->next)//安全检查，到达链表末尾则此趟就不进行比较			{				if (p->data>p->next->data)				{					temp = p->data;					p->data = p->next->data;					p->next->data = temp;				}				p = p->next;			}		}		p = head;//一趟比较完后再从头开始比较	}	return head;}node *insert_list(node *head, int val){	node *p1 = head;	node *p2 = NULL;	node *s = NULL;	s = (node *)malloc(sizeof(node));	s->data = val;	while (s->data>p1->data&&p1->next != NULL)	{//除了头节点和首节点后面还有节点，且插入值大于首节点值及后面的节点值，就双指针向后移动		p2 = p1;		p1 = p1->next;	}	if (s->data <= p1->data)	{//双指针后移，直到插入值小于或等于后面的节点值		if (head == p1)		{//除头节点，只有首节点,且插入值小于首节点值，插入到首节点之前			s->next = p1;			head = s;		}		else		{//插入到中间节点			p2->next = s;			s->next = p1;		}	}	else	{//插入到尾节点之后		p1->next = s;		s->next = NULL;	}	return head;}node *del_list(node *head, int val){	node *p1 = head;	node *p2 = NULL;	p1 = head;	while (val != p1->data&&p1->next != NULL)	{		p2 = p1;		p1 = p1->next;	}	if (val == p1->data)	{		if (p1 == head)		{			head = p1->next;//只有头节点，则删除它			free(p1);			p1 = NULL;		}		else		{			p2->next = p1->next;//删除p1所指向的节点			free(p1);			p1 = NULL;//防止野指针		}	}	else//如果不是出现要删除的整数使while循环停止，那么就是就是出现了p1->next==NULL，到达链表末尾，就说明没有出现该值		cout << endl << val << "could not been found" << endl;	return head;}node *combine_list(node *head1, node *head2){	if (NULL == head1)return head2;	if (NULL == head2)return head1;	node *head = NULL;	if (head1->data<head2->data)	{		head = head1;		head->next = combine_list(head1->next, head2);//递归实现	}	else	{		head = head2;		head->next = combine_list(head1, head2->next);	}	return head;}int main(){	node *head = NULL;	head = create_list();	cout << "生成1：";	print_list(head);	node *head1 = NULL;	head1 = create_list();	cout << "生成2：";	print_list(head1);	node *head2 = NULL;	head2 = combine_list(head, head1);	cout << "合并：";	print_list(head2);	head = sort_list(head);	cout << "排序：";	print_list(head);	head = insert_list(head, 2);	cout << "插入：";	print_list(head);	head = del_list(head, 2);	cout << "删除：";	print_list(head);	head = reverse_list(head);	cout << "逆置：";	print_list(head);	return 0;}