21. Merge Two Sorted Lists【easy】
2024-08-20 13:52:04
21. Merge Two Sorted Lists【easy】
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
解法一：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == NULL || l2 == NULL) {
return l1 ? l1 : l2;
} ListNode * dummy = new ListNode(INT_MIN);
ListNode * temp = dummy; while (l1 && l2) {
if (l1->val > l2->val) {
dummy->next = l2;
l2 = l2->next;
}
else {
dummy->next = l1;
l1 = l1->next;
} dummy = dummy->next;
} if (l1 || l2) {
dummy->next = l1 ? l1 : l2;
} return temp->next;
}
};
由于最后是弄到list1中，但是我们不知道list1还是list2的第一个元素关系，最后结果的list1中的头结点可能会改变，所以需要引入dummy节点。
解法二：
public ListNode mergeTwoLists(ListNode l1, ListNode l2){
if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val < l2.val){
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else{
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
参考了@yangliguang 的代码
解法三：
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
ListNode handler;
if(l1.val < l2.val) {
handler = l1;
handler.next = mergeTwoLists(l1.next, l2);
} else {
handler = l2;
handler.next = mergeTwoLists(l1, l2.next);
}
return handler;
}
}
参考了@RunRunCode 的代码
解法二和解法三都是递归，还没有完全弄明白……
最新文章
- Eclipse中的Link with Editor功能是如何实现
- C#设计模式-单例模式
- RabbitMQ中 exchange、route、queue的关系
- shell切割日志脚本
- （3）VS2010+Opencv-2.4.8的配置攻略
- java开发规范总结_代码注释规范
- swing的第一课
- 使用Visual Studio创建映像向导（Image Sprite）——Web Essential
- centos下 apache+mysql+php的安装
- Glide的 java.lang.RuntimeException: Expected instanceof GlideModule, but found:X.GlideModule@2e4554f
- Linux记录-linux系统监控命令汇总
- git迁移
- wvblk 把 xp、2003、win7（32位） 装入 VHD
- Unity AssetBoundle 打包流程
- [UE4]修改枪支碰撞体
- python文件相关操作
- __str__被print函数调用，目的是打印类的内容到屏幕上
- java中常见异常汇总（根据自己遇到的异常不定时更新）
- java 读入文件 FileInputStream
- Apache版Phoenix的安装（图文详解）