链表合并的两种方法

题目描述
将两个递增的链表合并为一个递增的链表
方法一：递归法
递归的思想自上而下，每次取出一个最小的节点指向递归找出的下一个最小的节点。
找的时候自上而下，但是结果的合并是自下而上(递归过程呈"V"字形)，因此只需将最后一个节点返回就是整个链表的头节点。

#include<iostream>
#include<algorithm>

using namespace std;

struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};
class Solution {
public:
	ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
	{
		if(pHead1==nullptr)return pHead2;
		if(pHead2==nullptr)return pHead1;
		if(pHead1->val<=pHead2->val){
			pHead1->next=Merge(pHead1->next, pHead2);
			return pHead1;
		}
		else{
			pHead2->next=Merge(pHead1,pHead2->next);
			return pHead2;
		}
	}
};

int main() {
	ListNode *x1 = new ListNode(1);
	ListNode *x2 = new ListNode(5);
	ListNode *x3 = new ListNode(5);

	ListNode *y1 = new ListNode(-1);
	ListNode *y2 = new ListNode(3);
	ListNode *y3 = new ListNode(7);

	ListNode *head;

	x1->next = x2;
	x2->next = x3;
	y1->next = y2;
	y2->next = y3;

	Solution s;
	head = s.Merge(x1, y1);
	while (head) {
		cout << head->val << " ";
		head = head->next;
	}
	return 0;
}

方法二：建立新的链表，迭代处理每一个节点

#pragma once
#include<iostream>
#include<algorithm>

using namespace std;


struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};
class Solution8 {
public:
	ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
	{
		if(pHead1==nullptr)return pHead2;
		if(pHead2==nullptr)return pHead1;
		ListNode *NewHead = new ListNode(-1);
		ListNode *node = NewHead;
		while (pHead1&&pHead2) {
			if (pHead1->val <= pHead2->val) {
				node->next = pHead1;
				pHead1 = pHead1->next;
			}
			else {
				node->next = pHead2;
				pHead2 = pHead2->next;
			}
			node = node->next;
		}
		if (pHead1) {
			node->next = pHead1;
		}
		else if (pHead2) {
			node->next = pHead2;
		}
		return NewHead->next;
	}
};

int main() {
	ListNode *x1 = new ListNode(1);
	ListNode *x2 = new ListNode(5);
	ListNode *x3 = new ListNode(5);

	ListNode *y1 = new ListNode(-1);
	ListNode *y2 = new ListNode(3);
	ListNode *y3 = new ListNode(7);

	ListNode *head;

	x1->next = x2;
	x2->next = x3;
	y1->next = y2;
	y2->next = y3;

	Solution s;
	head = s.Merge(x1, y1);
	while (head) {
		cout << head->val << " ";
		head = head->next;
	}
	return 0;
}

运算结果

最后

以上就是优美时光为你收集整理的链表合并的两种方法的全部内容，希望文章能够帮你解决链表合并的两种方法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。