题解 | #合并两个排序的链表#

合并两个排序的链表

https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337

//这题由于限制了空间复杂度为O1,因此最简单粗暴的办法,把两个链表遍历一边,所有值拿出来,存进数组,排序,建一个新链表,这种思路是不行的。我们只能在原地构建一个新链表——其实就是把几个指针大家挪来挪去,你指我指你。
//思路上借鉴了之前的反转链表的题解,想象成我们建了一个新的链表,然后把旧链表上的节点一个个“拆”下来,放到新链表上去。
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode* p1=pHead1;
		ListNode* p2=pHead2;
		ListNode* newList=new ListNode(0);//构造一个出来。不然空指针指向的空对象,也是没有成员对象next的。另外newList的存在主要是为了记录新链表的入口。
		ListNode* current=newList;
		while (p1 && p2) {
			if(p1->val > p2->val)
			{
				current->next=p2;//将current指向更小的那个节点,并移动current
				current=current->next;
				p2=p2->next;//移动p1
			}else {
				current->next=p1;
				current=current->next;
				p1=p1->next;
			}
		}
		current->next=p1? p1:p2;//剩下的直接整段接上去就行了。
		return newList->next;
    }
};

全部评论

相关推荐

05-07 17:58
门头沟学院 Java
wuwuwuoow:1.简历字体有些怪怪的,用啥写的? 2.Redis 一主二从为什么能解决双写一致性? 3.乐观锁指的是 SQL 层面的库存判断?比如 stock > 0。个人认为这种不算乐观锁,更像是乐观锁的思想,写 SQL 避免不了悲观锁的 4.奖项证书如果不是 ACM,说实话没什么必要写 5.逻辑过期时间为什么能解决缓存击穿问题?逻辑过期指的是什么 其实也没什么多大要改的。海投吧
简历中的项目经历要怎么写
点赞 评论 收藏
分享
07-02 10:44
门头沟学院 C++
码农索隆:太实诚了,告诉hr,你能实习至少6个月
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务