[数据结构与算法]将两个链表合成一个链表

方法1

#include<iostream>
using namespace std;
class List
{
private:
	typedef struct node
	{
		int data;
		node* next;
	}node;
	node* L1, * L2, * L3;//L1,L2合成L3
	node* R1, * R2;

public:
	List()//采用尾插法初始化各指针
	{
		L1 = new node;
		
		L1->next = NULL;
		R1 = L1;
		L2 = new node;
		L2->next = NULL;
		R2 = L2;
		L3 = NULL;
	}
	void Input()//输入数据
	{
		cout << "输入L1的结点数" << endl;
		int n;
		cin >> n;
		node* p;//负责数据输入的临时结点
		cout << "输入元素" << endl;
		for (int i = 0; i < n; ++i)
		{
			p = new node;
			cin >> p->data;
			R1->next = p;
			R1 = p;
		}
		R1->next = NULL;
		cout << "输入L2的节点数" << endl;
		cin >> n;
		cout << "输入元素" << endl;
		for (int i = 0; i < n; ++i)
		{
			p = new node;
			cin >> p->data;
			R2->next = p;
			R2 = p;
		}
		R2->next = NULL;
		OutPut();
	}
	void OutPut()//输出
	{
		cout << "L1的元素" << endl;
		for (node* p = L1->next; p; p = p->next)
			cout << p->data << '\t';
		cout << endl;
		cout << "L2的元素" << endl;
		for (node* p = L2->next; p; p = p->next)
			cout << p->data << '\t';
		cout << endl;
	}
	void Merge()//同时插入两两条链表的数据
	{
		L3 = L1;//直接令L3=L1免的开辟新的结点
		node* r = L3;//L3的尾结点
		node *p = L1->next;
		node* q = L2->next;
		delete L2;//此时不需要L2这个头结点了删去；
		while(p && q)
		{
			r->next = p; r = p; p = p->next;
			r->next = q; r = q; q = q->next;
		}
		//跳出循环有可能两个都为空跳出，也有可能一空一不空
		if (q) p = q;
		//当q不为空,令p=q,然后r->next直接指向p这样无论是q为空或p为空跳出都符合，且两者都为空时也符合
		r->next = p;
		cout << "合并后L3" << endl;
		for (node* p = L3->next; p; p = p->next)
			cout << p->data << '\t';
		cout << endl;
	}

方法2

void Merge2()//先将L1放到L3再将L2放到L3
	{
		L3 = L1;
		node* r = L3;
		for (node* p = L1->next; p; p = p->next)//将L1的元素一直放到L3中直到L1为空
		{
			r->next = p;
			r = p;
		}
		for (node* p = L2->next; p; p = p->next)
		{
			r->next = p;
			r = p;
		}
		r->next = NULL;
		delete L2;
		cout << "合并后L3" << endl;
		for (node* p = L3->next; p; p = p->next)
			cout << p->data << '\t';
		cout << endl;
	}

主函数

int main()
{
	List list;
	list.Input();
	list.Merge2();
}