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

打赏

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据