LeetCode 第21题 Merge Two Sorted Lists（Java）
原题地址： https://leetcode.com/problems/merge-two-sorted-lists/
要求
合并两个有序的链表，返回一个新链表。新的链表必须由前两个链表的节点组成。
例如:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
这道题的思路很简单，其实就是同时遍历两个链表，选择其中最小的一个节点，选了那个链表的元素，哪个链表就往前走一个，没有被选择的不动。在过程中，如果其中一个链表已经为空，那么就把另外一个链表的全部内容填充到结果链表里面。这是第一种解决方法，循环遍历。
上面思路很直接，但是代码看起来比较复杂，事实上，只要是链表这种结构，我们都可以考虑递归的去解决。思路如下面的代码，用递归来遍历。首先考虑，其中一个链表为空的情况，很简单直接把另一个链表返回。然后，如果l1的第一个节点比l2的第一节点小，或者相等，那么，就l1的第二个节点等于，现有l1的第二个节点和l2的合并结果，然后返回l1。反之亦然。
代码地址： https://github.com/tinyfool/leetcode/tree/master/src/p0021
正文到此结束
热门推荐
相关文章
Loading...
![[HBLOG]公众号](http://www.liuhaihua.cn/img/qrcode_gzh.jpg)
