题意概述

• 给定两个有序链表
• 将其连成一个有序链表

方法一：新建链表

思路与具体做法

• 先遍历两个链表上的所有结点保存权值在数组中
• 然后对其进行排序
• 根据排序后的数组建立一条权值有序的单链表

class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode *list=new ListNode(0);//新建链表 
		ListNode *p=list;//头指针
		int v[2020],cur=0; 
        while(pHead1){//遍历两个旧链表，保存权值
			v[cur++]=pHead1->val;
			pHead1=pHead1->next; 
		} 
		while(pHead2){
			v[cur++]=pHead2->val;
			pHead2=pHead2->next; 
		} 		
		sort(v,v+cur);//对权值进行排序
		int curr=0;
		while(curr<cur){//对排序后的权值依次新建结点
			p->next=new ListNode(v[curr++]); 
			p=p->next; 
		} 	
		return list->next;//返回结果链表
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O\left(n\right)O(n)$O(n)，遍历了2n个结点
• 空间复杂度：$O\left(n\right)O(n)$O(n)，使用了长度为n的数组，构建长度为n的链表

方法二：双指针

思路与具体做法

• 双指针，类比归并排序的“合并”步骤，将两个有序链表有序地合成一个链表
• 在两个链表的公共部分内，将较小的元素链接到新链表后
• 之后两个链表中若有某一个剩余，则直接链接到新的链表后

class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode *list=new ListNode(0);//新建链表 
		ListNode *p=list;
		while(pHead1&&pHead2){//在两个链表的公共部分，谁结点权值小连上谁 
			if(pHead1->val<pHead2->val){
				p->next=pHead1;
				pHead1=pHead1->next;				
			}else{
				p->next=pHead2;
				pHead2=pHead2->next;				
			}
			p=p->next;//指针后移 
		} 
		if(pHead1)p->next=pHead1;//两个链表谁有剩余，则接上 
		else p->next=pHead2;
		return list->next;
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O\left(n\right)O(n)$O(n)，遍历了2n个结点
• 空间复杂度：$O\left(1\right)O(1)$O(1)，无额外使用空间