合二为一
祝点赞关注的大佬们永不脱发！
合并有序链表
题目：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
今天的题目思路很简单，但是一遍AC也是不容易的。链表大部分题目考察的都是考生代码的完整性和鲁棒性，所以有些题目我们看着思路很简单，但是想直接通过还是需要下一翻工夫的，所以建议大家将我筛选的所有链表的题目都自己写一下。实在没有时间做的同学，可以自己在脑子里打一遍代码，想清每一行代码的作用。
迭代法：
因为我们有两个升序链表，我们需要将其合并，那么我们需要创建一个新节点（headpro），然后我们利用双指针思想，每个链表放置一个指针，然后进行遍历并对比当前指针指向的值。然后headpro.next指向较小值的那个节点，不断迭代，直至到达某一有序链表底部，此时一个链表遍历完成，然后我们将未完全遍历的链表接在我们接在合并链表之后即可。
这是我们迭代做法，另外这个题目还有一个递归方法，因为很多同学刚开始刷题所以目前先不写这个方法，防止绕晕。等链表掌握差不多的时候会单独写一篇递归解题框架的文章，也算是为树的题目做铺垫。
动图讲解：
合并链表
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode headpro = new ListNode(-1);//创建新的节点
ListNode headtemp = headpro; //遍历数组，看循环条件
while(l1!=null&&l2!=null){ //谁小指向谁
if(l1.val>=l2.val){
headpro.next = l2;
l2=l2.next;
}
else{
headpro.next = l1;
l1 = l1.next;
}
headpro = headpro.next;
} //将没有遍历完的添加到尾部
headpro.next=l1!=null?l1:l2;
return headtemp.next;
}
题目来源：leetcode 21. 合并两个有序链表
大家如果觉得这篇文章对大家有帮助的话，就请你将它转发给需要的人吧，顺便请大家点个关注和在看吧，创作不易。你们的支持对我真的帮助很大!每天都会为大家分享一道精选算法题，从简到难，我们一起坚持下去吧。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-10-26，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录