合并两个有序链表(leetcode21)
合并两个有序链表(leetcode21)
Vincent-yuan
发布于 2021-03-04 15:36:09
发布于 2021-03-04 15:36:09
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]解析：
方法一：递归
也就是说，两个链表头部值较小的一个节点与剩下元素的 merge 操作结果合并。
我们直接将以上递归过程建模，同时需要考虑边界情况。
如果 l1 或者 l2 一开始就是空链表 ，那么没有任何操作需要合并，所以我们只需要返回非空链表。
否则，我们要判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。
如果两个链表有一个为空，递归结束。
public class leetcode21 {
public static void main(String[] args) {
// TODO Auto-generated method stub
ListNode head1 = new ListNode(1);
head1.next = new ListNode(2);
head1.next.next = new ListNode(4);
ListNode head2 = new ListNode(1);
head2.next = new ListNode(3);
head2.next.next = new ListNode(4);
ListNode head = mergeTwoLists(head1,head2);
head.printNode(head);
}
//递归
public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1==null){//l1为空，则返回l2
return l2;
}else if(l2==null){//l2为空，则返回l1
return l1;
}else if(l1.val<l2.val){//l1的值小于l2的值，设置l1的next,同时返回l1
l1.next = mergeTwoLists(l1.next,l2);
return l1;
}else{//否则，设置l2的next，同时返回l2
l2.next = mergeTwoLists(l1,l2.next);
return l2;
}
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021-02-25 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读