【题目】
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.
【分析】
无
【代码】
/*********************************
* 日期:2015-01-06
* 作者:SJF0115
* 题目: 21.Merge Two Sorted Lists
* 来源:https://oj.leetcode.com/problems/merge-two-sorted-lists/
* 结果:AC
* 来源:LeetCode
* 博客:
**********************************/
#include <iostream>
using namespace std;
struct ListNode{
int val;
ListNode *next;
ListNode(int x):val(x),next(NULL){}
};
class Solution {
public:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
ListNode *head = new ListNode(-1);
ListNode *p1 = l1,*p2 = l2,*cur = head;
while(p1 != NULL && p2 != NULL){
// 取两个链表头的较小元素
if(p1->val < p2->val){
cur->next = p1;
p1 = p1->next;
}//if
else{
cur->next = p2;
p2 = p2->next;
}//else
cur = cur->next;
}//while
// 如果链表1没有遍历完
while(p1){
cur->next = p1;
p1 = p1->next;
cur = cur->next;
}//while
// 如果链表2没有遍历完
while(p2){
cur->next = p2;
p2 = p2->next;
cur = cur->next;
}//while
cur->next = NULL;
return head->next;
}
};
int main() {
Solution solution;
int A[] = {1,2,4,7,9};
int B[] = {3,5,8,10,11,12};
// 链表1
ListNode *head1 = new ListNode(A[0]);
ListNode *p1 = head1;
for(int i = 1;i < 5;i++){
ListNode *node = new ListNode(A[i]);
p1->next = node;
p1 = node;
}//for
// 链表2
ListNode *head2 = new ListNode(B[0]);
ListNode *p2 = head2;
for(int i = 1;i < 6;i++){
ListNode *node = new ListNode(B[i]);
p2->next = node;
p2 = node;
}//for
ListNode *head = solution.mergeTwoLists(head1,head2);
// 输出
ListNode *p = head;
while(p){
cout<<p->val<<" ";
p = p->next;
}//while
cout<<endl;
}
【代码二】
递归实现
class Solution {
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(l2->next, l1);
return l2;
}
}
};
【代码三】
public:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
ListNode *head = new ListNode(-1);
for(ListNode *p = head;l1 != NULL || l2 != NULL;p = p->next){
int val1 = (l1 == NULL) ? INT_MAX : l1->val;
int val2 = (l2 == NULL) ? INT_MAX : l2->val;
if(val1 <= val2){
p->next = l1;
l1 = l1->next;
}//if
else{
p->next = l2;
l2 = l2->next;
}//else
}//for
return head->next;
}
};
分享到:
相关推荐
第四章 Leetcode 题解 1. Two Sum 2. Add Two Numbers ...21. Merge Two Sorted Lists 22. Generate Parentheses 23. Merge k Sorted Lists 24. Swap Nodes in Pairs 25. Reverse Nodes in k-Group 26. Remove Dupli
LeetCode Merge 2 Sorted Lists解决方案
21.Merge Two Sorted Lists LeetCode 23.Merge k Sorted Lists(solve1) LeetCode 23.Merge k Sorted Lists(solve2) LeetCode 86.Partition List LeetCode 92.Reverse Linked List II LeetCode 138.Copy List with ...
lru缓存leetcode leetcode 1. Two Sum 2. Add Two Numbers 3. Longest Substring Without Repeating Characters 4. Median of Two Sorted Arrays 5. Longest Palindromic Substring 7. Reverse Integer 9. ...
lru缓存leetcode 力扣日记 欢迎来到我的 LeetCode 期刊库。 我的每个问题都将包括一个初始计划阶段,在这个阶段我将用我自己的话来定义问题,我将如何解决这个问题,并且所有内容都将首先用伪代码写出来。 当我解决...
【Leetcode】Merge Two Sorted Lists
leetcode 跳跃 leetcode 动态规划,背包问题 01背包问题:416. Partition Equal Subset Sum 最长回文:5. Longest Palindromic Substring - 字数组余数:523. Continuous Subarray Sum - 无重复字符的最长子串:3. ...
leetcode 答案 LeetCode-Trip LeetCode刷题代码,大佬勿入。 为一年后的研究生找工作准备 目标是BAT的算法岗哈哈哈哈哈 争取做到每日一更 嗯…… 19.10.22:鸽了这么久,我又回来了……主要在实验室天天没啥事,过于...
(https://leetcode.com/problems/remove-duplicates-from-sorted-array/)| [C++](./C++/remove-duplicates-from-sorted-array.cpp) [Python](./Python/remove-duplicates-from-sorted-array.py) | _O(n)_ | _O(1)_ |...
链接:https://leetcode-cn.com/problems/merge-k-sorted-lists 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 思路 很简单,因为是小的先插入,使用优先队列实现。把k个链表当前第一个...
leetcode添加元素使和等于 programmer_practices algorithm practices 最优解Book: 双栈实现getMin Stack. 双栈实现Queue. 递归和栈实现逆序操作一个栈. 仅用一个栈排序另一个栈. 打印两个有序链表的公共部分. 删除...
leetcode 2 sum c LeetCode 帮助文档 帮助文档存放在Help文件夹下。 文件名 文件描述 链接 complexitypython.txt Python的一些常规操作的复杂度统计 题目清单 Array(数组) ID Difficulty Title Java Python 1 Easy ...
leetcode中文版 LeetCode # Title Chinese Tag Solution 1 Two Sum 两数之和 array,hash 2 Add Two Numbers 两数相加 math 3 Longest Substring Without Repeating Characters 无重复字符的最长子串 string 4 ...
leetcode 2 Leetcode答案集 关于项目: 本项目包含本人LeetCode解题的答案,全部将由JavaScript语言进行解答。并会在每个题目的文件夹中添加相关的思路解析。 详情 # Title Solution Time Space Difficulty 1 Two ...
leetcode 答案LeetCode LeetCode in Swift 这个Repo 用来存下我在LeetCode 解题的原始档,包含解题中遇到的错误,也包含解出AC 的答案, 以下的清单将连结到我的Github Pages 中,皆有题目中文翻译与解题的过程。...
https://leetcode.com/problems/merge-two-sorted-lists/ 2D阵列 https://leetcode.com/problems/spiral-matrix/ https://leetcode.com/problems/search-a-2d-matrix/ ...
leetcode双人赛LeetCode 编号 题目 难度 题型 备注 Two Sum 简单 Add Two Numbers 中等 链结串列 重要 Longest Substring Without Repeating Characters 中等 字串 重要 Median of Two Sorted Arrays 困难 数学 ...
LeetCode 原创文章每周最少两篇,后续最新文章会在首发,视频首发,大家可以加我进交流群,技术交流或提意见都可以,欢迎Star!...Merge Two Sorted Lists 83 * Remove Duplicates from Sorted Lis
easy:21.Merge_Two_Sorted_Lists return a or b 首先我是第一次见到这种写法,查看了官方文档,引用如下: The expression x and y first evaluates x; if x is false, its value is returned; otherwise, y is ev
leetcode 分类leetcode 问题分类 leetcode代码仓库,我的解题思路写在我的博客里: leetcode 代码库,我博客上的解题思路: mkdir 列表: 大批 #1:Two Sum #4:Median of Two Sorted Arrays 地图 #1:Two Sum #3:...