【小浩算法cpp题解】合并两个有序链表(21)

前言

今天继续做链表相关的题目，考研期间练多了现在觉得这种题目真是简单。晚上如果有机会可以再做一个树的深度优先搜索。

我的思路

其实这道题的思路比较像排序中的二路归并，最核心的点是在归并的时候要防止断链,我的解决方法是设置一个selected_node,除此之外还需要考虑的点在于我们是想生成一个新的链表，还是说把一个链表归并到另一个，两者的区别其实不大，前者需要重新创建结点罢了。

我的代码

#include<iostream>
#include <unordered_map>
#include<vector>
using namespace std;

typedef struct Lnode {
	int data;
	struct Lnode* next;
	Lnode(int val) :
		data(val), next(NULL) {
	}
};

class LinkedList {
private:
	Lnode* head;
	Lnode* rear;
	int node_num=0;

public:
	LinkedList(vector<int> data) : head(nullptr), rear(head) {
		int nodeData;
		//把链表的总长度存储在头结点的数据域
		head = new Lnode(node_num);
		Lnode* p = head;
		Lnode* q;
		for (int i = 0; i < data.size(); i++) {
			this->node_num++;
			q = new Lnode(data[i]);
			p->next = q;
			p = p->next;
		}
		p = head->next;
		//输出生成的链表
		cout << "您已经生成如下链表: " << endl;
		while (p->next != NULL) {
			cout << p->data << " -> ";
			p = p->next;
		}
		cout << p->data << endl;
		rear = p;
	}

	~LinkedList() {
		Lnode* current = head;
		while (current != rear->next && current != nullptr) {
			Lnode* next = current->next;
			delete current;
			current = next;
		}
	}

	void printList() {
		//输出生成的链表
		cout << "=============链表如下：====== " << endl;
		Lnode* p = head;
		while (p->next != NULL) {
			cout << p->data << " -> ";
			p = p->next;
		}
		cout << p->data << endl;
		rear = p;
	}

	void append(int val) {
		rear->next = new Lnode(val);
		rear = rear->next;
	}

	Lnode* mergeList(Lnode* LinkList1, Lnode* LinkList2) {
		Lnode *r=this->head;
		Lnode* p = LinkList1->next, * q = LinkList2->next, * selectNode = nullptr;
		while (p != nullptr && q != nullptr) {
			if (p->data <= q->data) {
				selectNode = p;
				p = p->next;
			}
			else {
				this->node_num++;
				selectNode = q;
				q = q->next;
			}
			r->next = selectNode;
			r = r->next;
		}
		if (p != nullptr) {
			selectNode->next = p;
		}
		if (q != nullptr) {
			selectNode->next = q;
		}
		return head->next;
	}

	Lnode* getLinkList() {
		return head;
	}
};

int main() {
	vector<int> v1 = { 2,3,8 };
	vector<int> v2 = { 1,4,7 };
	LinkedList Llist(v1);
	LinkedList Llist2(v2);
	Lnode* newList_Merged = Llist.mergeList(Llist.getLinkList(), Llist2.getLinkList());
	cout << "==================== " << endl;
	cout << "您已经生成如下链表: " << endl;
	Lnode* p = newList_Merged;
	while (p->next != NULL) {
		cout << p->data << " -> ";
		p = p->next;
	}
	cout << p->data << endl;
	Lnode* del;
	return 0;
}