[数据结构与算法]2个有序链表的合并

#include <stdio.h>
#include <stdlib.h>

struct node
{
	unsigned int elem;
	struct node *next;
};

struct node *head = NULL;
struct node *tail = NULL;

void create_list(unsigned int elem);
void insert_node(int pos, unsigned int elem);
void delete_node(int pos);
void print_linklist(struct node *linklist_head);
int search(unsigned int elem);




int main(void)
{
	struct node *head1 = NULL;
	struct node *head2 = NULL;
	struct node *p = NULL;  //head1
	struct node *q = NULL;	//head2

	create_list(1);
	create_list(9);
	create_list(13);
	create_list(27);
	head1 = head;
	print_linklist(head1);

	head = NULL;
	create_list(3);
	create_list(5);
	create_list(14);
	create_list(81);
	create_list(88);
	create_list(95);
	create_list(99);
	head2 = head;
	print_linklist(head2);

	head = NULL;
	p = head1;
	q = head2;

	while(p && q)
	{
		if(p->elem <= q->elem)
		{
			if(head == NULL)
				head = p;
			else
				tail->next = p;
			tail = p;
			p = p->next;
		
		}
		else
		{
			if(head == NULL)
				head = q;
			else
				tail->next = q;
			tail = q;
			q = q->next;
		}
	}
	tail->next = p?p:q;
	
	print_linklist(head);

	return 0;
}


void create_list(unsigned int elem)
{
	struct node *p = (struct node *)malloc(sizeof(struct node));
	p->elem = elem;
	p->next = NULL;

	if(head == NULL)
		head = p;
	else
		tail->next = p;

	tail = p;
}

void insert_node(int pos, unsigned int elem)
{
	struct node *pre;
	pre = head;
	int i = 0;
	struct node *p = (struct node *)malloc(sizeof(struct node));

	if(pos == 0)
	{
		p->elem = elem;
		p->next = head;
		head = p;
	}
	else
	{
		while(i < pos - 1)
		{
			pre = pre->next;
			i++;
		}

		p->elem = elem;
		p->next = pre->next;
		pre->next = p;

		if(p->next == NULL)
			tail = p;
	}
}

void delete_node(int pos)
{
	struct node *pre, *p;
	pre = head;
	int i = 0;

	if(pos == 0)
	{
		head = head->next;
		free(pre);
	}
	else
	{
		while(i < pos - 1)
		{
			pre = pre->next;
			i++;
		}
	
		p = pre->next;
		pre->next = p->next;
		if(p->next == NULL)
			tail = pre;
		free(p);
	}
}

void print_linklist(struct node *linklist_head)
{
	struct node *p;

	for(p = linklist_head; p; p = p->next)
		printf("%5d", p->elem);

	printf("\n");
}

int search(unsigned int elem)
{
	struct node *p;

	for(p = head; p; p = p->next)
		if(p->elem == elem)
			return 1;
	return 0;
}