两个链表合并成有序链表的三种方法 C++实现

一、将第二个链表成员插入第一个链表

将第一个链表固定，扫描第二个链表，依次插入节点数据。

当p指针扫描到第二个链表的尾部时，p=NULL，退出扫描，链表合并结束。若第二个链表有数据要插在第一个链表表头前，要更换链表的头指针。区分头插，中间插，尾插。

代码实现如下：

#include<iostream>
using namespace std;
struct node
{
	int data;
	node* next;
};

void insertlist(node*& head, int n)//无序数据生成升序链表，单个数据插入基本法
{
	node* s, * p = NULL, * q = NULL;
	s = new node;
	s->data = n;
	s->next = NULL;
	if (head == NULL)
	{
		head = s;
		return;
	}

	if (head->data >= n) {
		s->next = head;
		head = s;
		return;
	}
	for (p = head, q = p->next;q;p = p->next, q = q->next)
	{
		if (q->data > n) {
			p->next = s;
			s->next = q;
			return;
		}

	}

	p->next = s;
	q = s;
	q->next = NULL;
	return;
}

void add(node*& head1, node* head2)//链表合并
{
	node* p=head2;
	while (p != NULL)
	{
		int n;
		n = p->data;
        //提取出第二个链表节点的数据
		insertlist(head1, n);//有序插入第一个链表
		p=p->next;
	}
	return;
}
void showlist(node* head)//链表的输出
{
	while (head != NULL)
	{
		cout << head->data << " ";
		head = head->next;
	}
    cout << endl;
}
int main()
{
	node* head1 = NULL, * head2 = NULL;
    //第一个链表的创建
	int n;cin >> n;
	while (n != 0)
	{
		insertlist(head1, n);
		cin >> n;
	}
	showlist(head1);
    //第二个链表的创建
	int m;cin >> m;
	while (m != 0)
	{
		insertlist(head2, m);
		cin >> m;
	}
	showlist(head2);
	//两个链表的合并
	add(head1, head2);
	showlist(head1);

}

二、将第二个链表节点有序插入第一个链表

会有三种情况：

（1）第二个链表是空的，第一个为空或者不为空都不做改变，返回原来第一个链表。

（2）第一个链表是空的，第二个链表不为空，直接将第一个链表头指针指向第二个链表头指针。

（3）两个链表都不为空，将第二个链表节点有序插入第一个链表。

让指针p指向head2的头指针，q从头指针head1依次向后扫描，找到大于p的节点，pre为前置指针，使得p插入pre和q中间，head2向后移动，p重新指向head2，重复进行。

代码实现如下：

#include<iostream>
using namespace std;
struct node
{
	int data;
	node* next;
};

void insertlist(node*& head, int n)//无序数据生成有序链表
{
	node* s, * p = NULL, * q = NULL;
	s = new node;
	s->data = n;
	s->next = NULL;
	if (head == NULL)
	{
		head = s;
		return;
	}

	if (head->data >= n) {
		s->next = head;
		head = s;
		return;
	}
	for (p = head, q = p->next;q;p = p->next, q = q->next)
	{
		if (q->data > n) {
			p->next = s;
			s->next = q;
			return;
		}

	}

	p->next = s;
	q = s;
	q->next = NULL;
	return;
}
void add(node*& head1, node* head2)
{

	if (head2 == NULL) return;//情况一：第二个链表为空，不做处理直接返回
	if (head1 == NULL)//情况二：第一个链表为空，将head1指向head2
	{
		head1 = head2;
		return;
	}
    //情况三：两个链表都不为空
	node* p = head1;
	node* q = head2;
	if (p->data > q->data)
	{
		head1 = q;
		head2 = head2->next;//段节点
		head1->next = p;

	}
	node* pre = NULL;//定义前置节点，用来记录插入位置前一个节点
	while (head2 != NULL)
	{

		while (p != NULL && p->data <= head2->data)
		{
			pre = p;
			p = p->next;
		}//找到比head2数据大的节点p

		q = head2;
		head2 = head2->next;//段节点
		q->next = p;
		pre->next = q;
		pre = pre->next;
		if (p == NULL) break;

	}
    //第二个链表节点还有剩余，全部依次尾插，此时pre指向最后一个有效节点
	while (head2 != NULL)
	{
		q = head2;
		head2 = head2->next;
		pre->next = q;
		pre = pre->next;

	}
	pre->next = NULL;

	return;
}


void showlist(node* head)
{
	while (head != NULL)
	{
		cout << head->data << " ";
		head = head->next;
	}
    cout << endl;
}

int main()
{
	node* head1 = NULL, * head2 = NULL;
    //建立第一个链表
	int n;cin >> n;
	while (n != 0)
	{
		insertlist(head1, n);
		cin >> n;
	}
	showlist(head1);
	
    //建立第二个链表
	int m;cin >> m;
	while (m != 0)
	{
		insertlist(head2, m);
		cin >> m;
	}
	showlist(head2);
    //建立合并链表
	add(head1, head2);
	showlist(head1);

}

三、将两个链表成一个新的有序链表

将两个链表节点断链，依次插入新链表，会有四种情况：

第一种：两个链表都是空链表

不做任何处理，直接返回空的head3。

第二种：第一个链表不为空，第二个链表为空

将head3指向第一个链表的头指针head1，返回head3。

第三种：第一个链表为空，第二个链表不为空，实现方式与第二种一样

第四种：两个链表都不为空

通过比较两个链表表头大小，建立新链表头指针head3，s指针指向新表头head3,p、q依次向后扫描，通过s-next指针向后插在第三个链表尾部。

代码实现如下：

#include<iostream>
using namespace std;
struct node
{
	int data;
	node* next;
};

void insertlist(node*& head, int n)//生成有序链表
{
	node* s, * p = NULL, * q = NULL;
	s = new node;
	s->data = n;
	s->next = NULL;
	if (head == NULL)
	{
		head = s;
		return;
	}

	if (head->data >= n) {
		s->next = head;
		head = s;
		return;
	}
	for (p = head, q = p->next;q;p = p->next, q = q->next)
	{
		if (q->data > n) {
			p->next = s;
			s->next = q;
			return;
		}

	}

	p->next = s;
	q = s;
	q->next = NULL;
	return;
}

node * addnew(node* head1, node* head2)//合并生成新有序链表
{
	node* head3 = NULL;
	head3 = new node;
	node* p, * q, * s;
	p = head1;
	q = head2;
    if(head1==NULL&&head2==NULL)//情况一：两个链表都为空
	{
		return head3;
	}
	else if(head1==NULL&&head2!=NULL)//情况二：链表1为空，链表1不为空
	{
		head3=head2;
		return head3;
	}
	else if(head2==NULL&&head1!=NULL)//情况三：链表2为空，链表1不为空
	{
		head3=head1;
		return head3;
	}
	//情况四：两个链表都不为空
	if (p->data < q->data)//比较大小，建立头指针
	{
		head3 = p;
		p = p->next;
	}
	else

	{
		head3 = q;
		q = q->next;
	}

	s = head3;

	while (p != NULL && q != NULL)
	{
		if (p->data < q->data)
		{
			s->next = p;
			s = s->next; 
			p = p->next;
			
		}
		else if (p->data >= q->data)

		{
			s->next = q;
			s = s->next;
			q = q->next;
		}
	}

	if (p != NULL&&q==NULL)//链表1还有剩余
	{
		while (p != NULL)
		{

			s->next = p;
			s = s->next; 
			p = p->next;


		}
		s->next = NULL;

	}
	else if (q != NULL&&p==NULL)//链表1还有剩余
	{
		while (q != NULL)
		{

			s->next = q;
			s = s->next; 
			q = q->next;

		}
		s->next = NULL;
	}
	else if (p == NULL && q == NULL) s->next = NULL;//链表1和2都插入完成
	
	return head3;//返回新链表的头指针
}

void showlist(node* head)
{
	while (head != NULL)
	{
		cout << head->data << " ";
		head = head->next;
	}
    cout<<endl;
}

int main()
{
	node* head1 = NULL, * head2 = NULL;
    //创建第一个链表
	int n;cin >> n;
	while (n != 0)
	{
		insertlist(head1, n);
		cin >> n;
	}
	showlist(head1);
    //创建第二个链表
	int m;cin >> m;
	while (m != 0)
	{
		insertlist(head2, m);
		cin >> m;
	}
	showlist(head2);
	//生成新链表
	node* head3;
	head3 = addnew(head1, head2);
	showlist(head3);

}

若文章出现错误，恳请各界人士指正，衷心感谢！