原题
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入： 1->2->4, 1->3->4
输出： 1->1->2->3->4->4
解法
思想
比较两个有序链表的头指针指向的值，取其中值更小的连接到一个哨兵节点后面，然后该链表的头指针向后移一格，继续和另一个节点的头指针比较。
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode virtualHead = new ListNode(0);
ListNode cur = virtualHead;
ListNode min;
while(l1!=null || l2 != null){
min = null;
if(l1==null || l2!=null&&l1.val>=l2.val){
min = l2;
l2 = l2.next;
}
else if(l2==null || l1!=null&&l2.val>l1.val){
min = l1;
l1 = l1.next;
}
cur.next = min;
cur = cur.next;
}
return virtualHead.next;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode21-%e5%90%88%e5%b9%b6%e4%b8%a4%e4%b8%aa%e6%9c%89%e5%ba%8f%e9%93%be%e8%a1%a8/
相关推荐
-
leetcode1114-按序打印
原题 我们提供了一个类： public class Foo { public void one() { print("one"); } public void two() ...
-
leetcode435-无重叠区间
原题 给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。 注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没...
-
leetcode622-设计循环队列
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是...
-
leetcode983-最低票价
原题 在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。 火车...
-
'leetcode50-Pow(x,n)'
原题 实现 pow(x, n) ，即计算 x 的 n 次幂函数。 示例1： 输入： 2.00000, 10 输出： 1024.00000 示例2： 输入： 2.10000, 3 输...
-
leetcode225--用队列实现栈
原题 使用队列实现栈的下列操作： push(x) – 元素 x 入栈 pop() – 移除栈顶元素 top() – 获取栈顶元素 empty() – 返回栈是否为空 注意: 你只能...
-
leetcode456-132模式
原题 给定一个整数序列：a1, a2, ..., an，一个132模式的子序列 ai, aj, ak 被定义为：当 i < j < k 时，ai < ak <...
-
leetcode739-每日温度
原题 根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。 例如，给定一个列表 te...
-
leetcode54-螺旋矩阵
原题 给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。 示例 1: 输入: [ [ 1, 2, 3 ], [ 4, 5, 6...
-
leetcode80-删除排序数组中的重复项II
原题 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外...