摘要:题目要求翻译过来就是将两个有序的链表组合成一个新的有序的链表思路一循环在当前两个链表的节点都是非空的情况下比较大小,较小的添入结果链表中并且获得较小节点的下一个节点。
题目要求
</>复制代码
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.
翻译过来就是:将两个有序的链表组合成一个新的有序的链表
思路一:循环在当前两个链表的节点都是非空的情况下比较大小,较小的添入结果链表中并且获得较小节点的下一个节点。这样比较直至至少遍历完一个链表。再将剩下的链表添至结果链表的末端
</>复制代码
public class MergeTwoSortedLists_21 {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode start = new ListNode(0);
ListNode temp = new ListNode(0);
start.next = temp;
while(l1!=null && l2!=null){
if(l1.val <= l2.val){
temp.next = l1;
l1 = l1.next;
}else{
temp.next = l2;
l2 = l2.next;
}
temp = temp.next;
}
if(l1!=null){
temp.next = l1;
}
if(l2!=null){
temp.next = l2;
}
return start.next.next;
}
public class ListNode{
int val;
ListNode next;
ListNode(int x) { val = x; }
}
}
思路二:递归
每次比较得到两个节点中较小的节点作为结果返回,并继续对剩下来的链表重新获得较小节点。
</>复制代码
public class MergeTwoSortedLists_21 {
public ListNode mergeTwoLists_recursive(ListNode l1, ListNode l2){
if(l1==null){
return l2;
}else if (l2==null){
return l1;
}
ListNode mergeHead;
if(l1.val <= l2.val){
mergeHead = l1;
mergeHead.next = mergeTwoLists_recursive(l1.next, l2);
}else{
mergeHead = l2;
mergeHead.next = mergeTwoLists(l1, l2.next);
}
return mergeHead;
}
public class ListNode{
int val;
ListNode next;
ListNode(int x) { val = x; }
}
}
想要了解更多开发技术,面试教程以及互联网公司内推,欢迎关注我的微信公众号!将会不定期的发放福利哦~
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/66984.html
摘要:题目详情题目要求我们将两个有序链表合成一个有序的链表。输入输出想法首先要判断其中一个链表为空的状态,这种情况直接返回另一个链表即可。每次递归都会获得当前两个链表指针位置的值较小的节点,从而组成一个新的链表。 题目详情 Merge two sorted linked lists and return it as a new list. The new list should be mad...
摘要:将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。无非是依次将两个链表每个节点的值对比,取出值较小的节点,添加到新链表末尾。将剩余链表传回递归函数。 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 Merge two sorted linked lists and return it as a n...
摘要:什么意思呢比如上方合并链表的代码,分别明确函数的参数和返回值是什么参数是两个合并的链表结点头结点。返回值是合并后的链表。 Time:2019/4/9Title: Merge Two Sorted ListsDifficulty: EasyAuthor: 小鹿 题目:Merge Two Sorted Lists Merge two sorted linked lists and re...
摘要:注意因为堆中是链表节点,我们在初始化堆时还要新建一个的类。代码初始化大小为的堆拿出堆顶元素将堆顶元素的下一个加入堆中 Merge Two Sorted Lists 最新更新请见:https://yanjia.me/zh/2019/01/... Merge two sorted linked lists and return it as a new list. The new list...
摘要:分治算法递归每层操作分解将原问题分解成一系列的子问题。分治算法满足的条件可分解原问题与分解成的小问题具有相同的模式无关联原问题分解成的子问题可以独立求解,子问题之间没有相关性,这一点是分治算法跟动态规划的明显区别。 Time:2019/4/10Title: Merge K Sorted ListsDifficulty: DifficultyAuthor: 小鹿 题目:Merge K...
阅读 3984·2021-10-12 10:12
阅读 1665·2021-10-11 10:58
阅读 2503·2021-10-09 10:01
阅读 2763·2021-09-24 09:48
阅读 2863·2021-09-09 11:38
阅读 3664·2019-08-30 15:44
阅读 1882·2019-08-30 14:22
阅读 675·2019-08-29 12:42