C++实现两个单链表有序合并

#include
using namespace std;
typedef int T;

class Node
{
public:
	void Setdata(int data);
	void Setnext(Node *next);
	T Getdata();
	Node* Getnext();

private:
	T m_Data;
	Node* m_Next;
};

void Node::Setdata(T data)
{
	m_Data = data;
}

void Node::Setnext(Node* next)
{
	m_Next = next;
}

T Node::Getdata()
{
	return m_Data;
}

Node* Node::Getnext()
{
	return m_Next;
}

class LinkList
{
public:
	LinkList();     //初始化单链表
	~LinkList();     //销毁
	bool CreateList();  //创建单链表
	void EmptyList();  //判断是否 为空
	int LengthList();  //获取长度
	void ShowList();   //遍历输出
	bool InsertLinkList(); //指定位置插入指定数据
	bool LocateDelLinkList();  //删除指定位置元素
	bool ElemDeleLinkList();  //删除指定值
	bool SortLinkList();    //排序
	void MergeLinkList(LinkList& L1, LinkList& L2);  //归并两个单链表

private:
	Node* m_Head;
};

LinkList::LinkList()  //初始化单链表（头节点）
{
	m_Head = new Node; 
	m_Head->Setdata(0);
	m_Head->Setnext(NULL);
}
 
LinkList::~LinkList()   //销毁
{
	Node* p;
	while (m_Head->Getnext()) {
		p = m_Head;
		m_Head = m_Head->Getnext();  //m_Head指针依次后移，依次删除结点，头节点后移
		delete p;
	}
	m_Head->Setnext(NULL);
	m_Head->Setdata(0);
}

bool LinkList::CreateList()  //创建单链表
{
	T k = 0;
	cout << "请输入链表长度" << endl;  cin >> k;
	Node* pnew, * ptemp;
	ptemp = m_Head;
	for (int i = 0; i < k; i++)
	{
		T e = 0;
		cout << "请输入数据：" << " ";  cin >> e;  cout << endl;
		pnew = new Node;
		pnew->Setdata(e);
		pnew->Setnext(NULL);
		ptemp->Setnext(pnew);
		ptemp = pnew;
	}
	return true;
}

void LinkList::EmptyList() //判断是否 为空
{
	if (m_Head->Getnext() == NULL) {
		cout << "空表" << endl;
	}
	else {
		cout << "非空" << endl;
	}
}

int LinkList::LengthList()  //获取长度
{
	int j = 0;  //初始化计数器
	Node* ptemp;
	ptemp = m_Head;
	while (ptemp->Getnext()) {
		ptemp = ptemp->Getnext();
		j++;
	}
	cout << "表长为：" << j << endl;
	return j;
}

void LinkList::ShowList()   //遍历输出
{
	Node* ptemp;
	ptemp = m_Head;
	while (ptemp->Getnext()) {
		ptemp = ptemp->Getnext();
		cout << "表中数据为：" << ptemp->Getdata() << " ";
	}
	cout << endl;
}

bool LinkList::InsertLinkList() //指定位置插入指定数据
{
	int i, e = 0;  int j = 0;
	cout << "请输入插入位置：" << " ";  cin >> i; cout << endl;
	cout << "请输入插入数据：" << " ";  cin >> e; cout << endl;
	Node* pnew,*ptemp;   //工作指针
	ptemp = m_Head;
	while (ptemp && j < i - 1) {
		ptemp = ptemp->Getnext();
		j++;
	}
	pnew = new Node;
	pnew->Setdata(e);
	pnew->Setnext(ptemp->Getnext());
	ptemp->Setnext(pnew);
	return true;
}

bool LinkList::LocateDelLinkList() //删除指定位置元素
{
	int i, j = 0;
	cout << "请输入删除位置：" << " ";  cin >> i; cout << endl;
	Node* ptemp;
	ptemp = m_Head;
	while (ptemp->Getnext() && j < i - 1) {
		ptemp = ptemp->Getnext();
		j++;
	}
	ptemp->Setnext((ptemp->Getnext())->Getnext());
	return true;
}

bool LinkList::ElemDeleLinkList()  //删除指定值
{
	int e = 0;
	cout << "输入删除的数值：" << " ";  cin >> e; cout << endl;
	while (m_Head != NULL && m_Head->Getdata() == e) {
		// 排除链表头指定值的情况
		Node* ptemp;  ptemp = m_Head;
		m_Head = m_Head->Getnext();
		delete ptemp;
	}

	Node* ptemp, * qtemp;// p：较快地指针, q：较慢指针
	ptemp = qtemp = m_Head;
	while (ptemp != NULL) {
		if (ptemp->Getdata() == e) {// 第一个p肯定不会是data
			qtemp->Setnext(ptemp->Getnext());
			delete ptemp;
			ptemp = qtemp->Getnext();
		}
		else {
			qtemp = ptemp;
			ptemp = ptemp->Getnext();
		}
	}
	return true;
}

bool LinkList::SortLinkList()    //排序
{
	Node* p, * q;
	p = m_Head->Getnext();
	while (p!= NULL) {
		q = p->Getnext();
		while (q != NULL) {
			if (p->Getdata() > q->Getdata())
			{
				int i = 0;
				i = p->Getdata();
				p->Setdata(q->Getdata());
				q->Setdata(i);
			}
			q = q->Getnext();
		}
		p = p->Getnext();
	}
	return true;
}

void LinkList::MergeLinkList(LinkList& L1, LinkList& L2)  //归并两个单链表
{
	L1.SortLinkList(); L2.SortLinkList();
	Node* a, * b, * c;
	c = L1.m_Head;
	a = L1.m_Head->Getnext();  b = L2.m_Head->Getnext();
	while (a && b) {
		if (a->Getdata() >= b->Getdata()) {
			c->Setnext(b);
			c = c->Getnext();
			b = b->Getnext();
		}
		else {
			c->Setnext(a);
			c = c->Getnext();
			a = a->Getnext();
		}
		if (c->Getnext() == a) {
			c->Setnext(b);
		}
		else {
			c->Setnext(a);
		}
	}
	delete L2.m_Head;
}

int main()
{
	

	LinkList L1;
	LinkList L2;
	L1.CreateList();
	L1.ShowList();
	L2.CreateList();
	L2.ShowList();


	L1.MergeLinkList(L1, L2);
	L1.ShowList();

	
	

	system("pause");
	return 0;
}

 实现效果如下：