LeetCode 热题 100_合并两个有序链表（27_21_简单_C++）（单链表；迭代）

题目描述：

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

输入输出样例：

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：
输入：l1 = [], l2 = []
输出：[]

示例 3：
输入：l1 = [], l2 = [0]
输出：[0]

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

题解：

解题思路：

思路一（迭代）：
1、通过题目分析，将两个升序链表合并为一个新的 升序 链表并返回。我们可以将两个链表中较小的结点 插入到合并链表，直至两个链表结束。

2、具体思路如下：
① 创建一个临时结点当作连接两个链表的头结点。
② 每次将值较小的结点连接到合并链表，采用尾插法进行合并。

3、复杂度分析
① 时间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。因为每次循环迭代中，list1 和 list2 只有一个元素会被放进合并链表中， 因此 while 循环的次数不会超过两个链表的长度之和。因此总的时间复杂度为 O(n+m)。
② 空间复杂度：O(1)。我们只需要常数的空间存放若干变量。

代码实现（思路一（迭代））：

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
	//创建一个临时结点当作连接两个链表的头结点 
	ListNode *prehead=new ListNode(-1);
	//采用尾插法进行合并 
	ListNode *tail=prehead;
	//每次将值较小的结点连接到合并链表 
	while(list1!=nullptr&&list2!=nullptr){
		if(list1->val<list2->val){
			tail->next=list1;
			list1=list1->next;
		}else{
			tail->next=list2;
			list2=list2->next;
		}
		//每次都连接一个结点后，tail向后移动一次记录末尾 
		tail=tail->next;
	}
	//注意这里连接一个结点，就是连接一串结点(未连接部分本来就是链表) 
	tail->next=(list1!=nullptr) ? list1 : list2;
	
	//注意合并的结点是从第二个结点开始 
	return prehead->next;
}

完成思路一的代码调试

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

struct ListNode{
	int val;
	ListNode *next;
	ListNode():val(0),next(nullptr){}
	ListNode(int x):val(x),next(nullptr){}
	ListNode(int x,ListNode *next):val(x),next(next){}
};

//创建单链表
ListNode *createList(vector<int> arr){
	ListNode *head=nullptr,*tail=nullptr;
	for(const auto val:arr){
		ListNode* newNode=new ListNode(val);
		if(head==nullptr){
			head=newNode;
			tail=newNode;
		}else{
			tail->next=newNode;
			tail=newNode;
		}
	}
	return head;
}

//将两个单链表进行合并
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
	//创建一个临时结点当作连接两个链表的头结点 
	ListNode *prehead=new ListNode(-1);
	//采用尾插法进行合并 
	ListNode *tail=prehead;
	//每次将值较小的结点连接到合并链表 
	while(list1!=nullptr&&list2!=nullptr){
		if(list1->val<list2->val){
			tail->next=list1;
			list1=list1->next;
		}else{
			tail->next=list2;
			list2=list2->next;
		}
		//每次都连接一个结点后，tail向后移动一次记录末尾 
		tail=tail->next;
	}
	//注意这里连接一个结点，就是连接一串结点(本来就是链表) 
	tail->next=(list1!=nullptr) ? list1 : list2;
	//注意prehead是new创建出来的结点，函数结束不会自动释放需要delete进行释放
	//使用list1指向合并链表的首节点
	list1=prehead->next;
	delete prehead;
	return list1;
}

int main(){
	vector<int> a={1,2,4};
	vector<int> b={1,3,4};
	ListNode *list1=createList(a);
	ListNode *list2=createList(b);
	ListNode *mergeList=mergeTwoLists(list1,list2);
	while(mergeList!=nullptr){
		cout<<mergeList->val<<"->";
		mergeList=mergeList->next;
	}
	cout<<"null";
	return 0;
} 

LeetCode 热题 100_合并两个有序链表（27_21)原题链接
欢迎大家和我沟通交流(✿◠‿◠)