C语言(每日一题)——数据结构——归并两条有序链表(详细过程)

下面会给出两种不同的方法，思路不一样，但是都可以达到我们要的结果
方法1是拆一条链表，方法2是两条都拆，方法1代码可能更容易懂一些

定义结构体

#include //printf
#include //malloc
#include //strlen

typedef int Elemtype; //数据元素的类型
//定义数据节点
typedef  struct node
{
    Elemtype data;  //数据域：保存数据本身用的
    struct node *next; //指针域：用来保存关系用的，保存下一个数据节点的地址
    
}Node;

Node *Merger_TwoLinklist1(Node *list1,Node *list2)
{
	//思路：将其中一条链表拆下来并有序的插入到另一条链表中去
	Node *pnew = NULL;
	Node *p = NULL;
	Node *pre = NULL;

	while(list2)
	{
		//1.将list2中的首节点拆下来
		pnew = list2;
		list2 = list2->next;
		pnew->next = NULL;

		//2.在list1中找pnew的插入位置
		p = list1;
		pre = NULL;
		while(p)
		{
			if(p->data > pnew->data)//找第一个比pnew->data大的节点,pnew就插入到这个节点的前面
			{
				break;
			}
			pre = p;
			p = p->next;
		}

		//3.分情况讨论插入
		if(p == list1)//插入到list1的首节点的前面
		{
			pnew->next = list1;
			list1 = pnew;
		}
		else//插入到list1的中间节点或者尾结点的前面或者pnew->data是最大值尾插
		{
			pre->next = pnew;
			pnew->next = p;
		}
	}
	return list1;
}

Node *Merger_TwoLinklist2(Node *list1,Node *list2)
{
	//思路：比较两条链表的首节点的大小，将值小的首节点拆下来组成一条新的链表
	Node *head = NULL;
	Node *tail = NULL;
	Node *pnew = NULL;

	while(list1 && list2)
	{
		//1.比较两条链表的首节点的大小将值小的首节点拆下来
		if(list1->data < list2->data)
		{
			//拆list1的首节点
			pnew = list1;
			list1 = list1->next;
			pnew->next = NULL;
		}
		else
		{
			//拆list2的首节点
			pnew = list2;
			list2 = list2->next;
			pnew->next = NULL;
		}

		//2.直接尾插到新链表中
		if(head == NULL)
		{
			head = tail = pnew;
		}
		else 
		{
			tail->next = pnew;
			tail = pnew;
		}
	}

	tail ? (tail->next = list1 ? list1 : list2) : (head = list1 ? list1 : list2);

	return head;
}

void Print_Linklist(Node *list)
{
    Node *p = list;
    while(p){
        printf("%d ",p->data);
        p = p->next;
    }
  putchar('n');
}

//以链式结构(链表)的方式去保存线性表中的数据。
int main()
{
	//归并两条有序链表
	//有序链表的创建可以参考我之前发的创建有序链表的代码这里我直接引用，不做解释了
	Node *list1 = Create_SortLinklist();//list1指向创建出来的有序单链表的首节点
	Node *list2 = Create_SortLinklist();//list2指向创建出来的有序单链表的首节点
	
	//这里两种方法都可以归并链表，这里使用第二种，下面也给出第二种的结果
	//Node *list = Merger_TwoLinklist1(list1,list2);
	Node *list = Merger_TwoLinklist2(list1,list2);
	Print_Linklist(list);
	return 0;
}

**运行结果**

大家有什么问题可以私信我哦！