单链表的实现_单链表数据插入: insertnode(snode *head, int pos, int valu

typedef struct node
{
	int data;
	node *next;
}node;
 
 
node* Create();                                // 创建单链表
int length(node *head);                        // 计算单链表的长度
void print(node *head);                        // 单链表的打印
node* search_node(node* head, int pos);        // 单链表节点的查找,从0开始，0返回head节点
bool insert_node(node* head, int pos, int data); // 在第pos个节点之后插入节点
bool delete_node(node* head, int pos);        // 删除第pos个节点
void reverse(node* head);                     // 单链表逆置
node* search_mid(node* head);                      // 寻找单链表的中间节点
void insert_sort(node* head);                        // 单链表的正向排序
bool isLoop(node* head, node* start);          // 判断单链表是否存在环,start存放环的入口节点
void mergeLink(node* head1, node* head2);     // 有序单链表合并
 
node* Create()                                 // 创建单链表
{
	cout << "======================Create()=====================" << endl;
	node* head = (node*)malloc(sizeof(node));
	assert(head != NULL);
	head->data = -1;
	bool isFirst = true;                      // 是否为第一个节点
	node* p = head;
	node* q = NULL;
	int temp;
	while (cin >> temp)
	{
		if (temp == 0)
		{
			break;
		}
		p = (node*)malloc(sizeof(node));
		assert(p!=NULL);
		p->data = temp;
		if (isFirst)
		{
			isFirst = false;
			head->next = p;			
		}
		else
		{
			q->next = p;
		}
		q = p;
	}
	p->next = NULL;
 
	return head;
}
int length(node *head)                        // 计算单链表的长度
{
	cout << "==========================length()==========================" << endl;
	int count = 0;
	node* p = head->next;
	while (p != NULL)
	{
		count++;
		p = p->next;
	}
	return count;
}
void print(node *head)                        // 单链表的打印
{
	cout << "==========================print()==========================" << endl;
	node* p = head->next;
	while (p != NULL)
	{
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
}
node* search_node(node* head, int pos)        // 单链表节点的查找,从0开始，0返回head节点
{
	cout << "==========================search_node()==========================" << endl;	
	if (pos < 0)
	{
		return NULL;
	}
	int count = 0;
	node* p = head;
	while (p != NULL)
	{
		if (count == pos)
		{
			return p;
		}
 
		count++;
		p = p->next;
	}
	return NULL;
}
bool insert_node(node* head, int pos, int data) // 在第pos个节点之后插入节点
{
	cout << "==========================insert_node()==========================" << endl;		
	if (pos < 0)
	{
		return false;
	}
	node* p = search_node(head, pos);
	if (p != NULL)               // p是尾节点或者中间节点
	{
		node* q = (node*)malloc(sizeof(node));
		assert(q != NULL);
		q->data = data;
		q->next = p->next;
		p->next = q;
		return true;
	}
	return false;
}
bool delete_node(node* head, int pos)        // 删除第pos个节点,pos不能为0
{
	cout << "==========================delete_node()==========================" << endl;
	if (pos <= 0)
	{
		return false;
	}
	node* q = search_node(head, pos-1);     // 记录第pos个节点的前驱pos-1
	node* p = q->next;                      // 记录第pos个节点
	if (p != NULL)                          // 删除节点P               
	{
		q->next = p->next;
		delete p;
		p = NULL;
		return true;
	}
	return false;
}
void reverse(node* head)                     // 单链表逆置
{
	cout << "==========================reverse()==========================" << endl;
	node* p = head->next;                    // p用于遍历链表
	node* q;
	head->next = NULL;
	while (p != NULL)
	{
		q = p;                              // 记录当前节点
		p = p->next;
 
		q->next = head->next;             // 将节点p用头插法插入链表
		head->next = q;		
	}
}
node* search_mid(node* head)                      // 寻找单链表的中间节点
{
	cout << "==========================search_mid()==========================" << endl;
	int i = 0;
	int j = 0;
	node* current = head->next;
	node* mid = head->next;
	while (current != NULL)
	{
		if (i / 2 > j)
		{
			j++;
			mid = mid->next;
		}
		i++;
		current = current->next;
	}
	return mid;	
}
void insert_sort(node* head)                       // 单链表的正向排序(升序)
{
	cout << "==========================insert_sort()==========================" << endl;
	if (head==NULL || head->next == NULL || head->next->next==NULL)
	{
		return;
	}
	node* p = head->next->next;                   // 第二个节点
	node* r = NULL;
	head->next->next = NULL;                      // 保留第一个节点，后续的节点使用插入排序
	node* pre = head;
	node* cur = head->next;
 
	while (p != NULL)
	{
		pre = head;
		cur = head->next;
		r = p;
		p = p->next;
		while (cur != NULL && cur->data < r->data)
		{
			cur = cur->next;
			pre = pre->next;
		}
		pre->next = r;
		r->next = cur;
	}
}
bool isLoop(node* head, node* start)          // 判断单链表是否存在环,start存放环的入口节点
{
	cout << "==========================isLoop()==========================" << endl;
	if (head == NULL && head->next == NULL)
	{
		return false;
	}
	node* p = head;
	node* q = head;
	while (q!=NULL && q->next!=NULL && p!=q)
	{ 
		p = p->next;                  // 慢指针
		q = q->next->next;            // 快指针
	}
	if (p == q)
	{
		return true;
	}
	return false;
}
// 依次将第二个链表中的节点插入到第一个链表中
void mergeLink(node* head1, node* head2)     // 有序单链表合并
{
	cout << "==========================mergeLink()==========================" << endl;
	if (head1 == NULL || head1->next == NULL || head2 == NULL || head2->next == NULL)
	{
		return;
	}
	node* p = head2->next;                    // 第二个链表
	node* r = head2;
 
	node* pre = head1;                        // 第一个链表
	node* cur = head1->next;
 
	while (p != NULL)
	{
		pre = head1;
		cur = head1->next;
		r = p;
		p = p->next;
		while (cur != NULL && cur->data < r->data)
		{
			cur = cur->next;
			pre = pre->next;
		}
		pre->next = r;
		r->next = cur;
	}
}