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

目录

• 前言
• 我的思路
• 我的代码

  前言

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

  我的思路

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

  我的代码

  #include
  #include 
  #include
  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 data) : head(nullptr), rear(head) {
  		int nodeData;
  		//把链表的总长度存储在头结点的数据域
  		head = new Lnode(node_num);
  		Lnode* p = head;
  		Lnode* q;
  		for (int i = 0; i node_num++;
  			q = new Lnode(data[i]);
  			p->next = q;
  			p = p->next;
  		}
  		p = head->next;
  		//输出生成的链表
  		cout 
  			cout next;
  		}
  		cout data 
  		Lnode* current = head;
  		while (current != rear-next && current != nullptr) {
  			Lnode* next = current->next;
  			delete current;
  			current = next;
  		}
  	}
  	void printList() {
  		//输出生成的链表
  		cout 
  			cout next;
  		}
  		cout data 
  		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 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 v1 = { 2,3,8 };
  	vector v2 = { 1,4,7 };
  	LinkedList Llist(v1);
  	LinkedList Llist2(v2);
  	Lnode* newList_Merged = Llist.mergeList(Llist.getLinkList(), Llist2.getLinkList());
  	cout 
  		cout 

手机扫描二维码访问