leetcode21 Merge Two Sorted Lists 将两个有序链表组合成一个新的有

BothEyes1993 发布于2019-08-14 18:05 / 2110人阅读

摘要：题目要求翻译过来就是将两个有序的链表组合成一个新的有序的链表思路一循环在当前两个链表的节点都是非空的情况下比较大小，较小的添入结果链表中并且获得较小节点的下一个节点。

题目要求

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; }
    }
}

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

专线服务混合云购买一个新的主机 c语言将链表数据存储 linux将硬盘分成两个区两个网站一个域名

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66984.html

Leetcode 21 Merge Two Sorted Lists

摘要：题目详情题目要求我们将两个有序链表合成一个有序的链表。输入输出想法首先要判断其中一个链表为空的状态，这种情况直接返回另一个链表即可。每次递归都会获得当前两个链表指针位置的值较小的节点，从而组成一个新的链表。题目详情 Merge two sorted linked lists and return it as a new list. The new list should be mad...

xbynet 2019-08-14 18:01 评论0 收藏0
LeetCode 21：合并两个有序链表 Merge Two Sorted Lists

摘要：将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。无非是依次将两个链表每个节点的值对比，取出值较小的节点，添加到新链表末尾。将剩余链表传回递归函数。将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 Merge two sorted linked lists and return it as a n...

LeviDing 2019-07-31 11:31 评论0 收藏0
LeetCode 之 JavaScript 解答第21题 —— 合并两个有序链表（Merge Two

摘要：什么意思呢比如上方合并链表的代码，分别明确函数的参数和返回值是什么参数是两个合并的链表结点头结点。返回值是合并后的链表。 Time：2019/4/9Title: Merge Two Sorted ListsDifficulty: EasyAuthor: 小鹿题目：Merge Two Sorted Lists Merge two sorted linked lists and re...

wdzgege 2019-08-23 16:51 评论0 收藏0
[Leetcode] Merge Two Sorted Lists Merge K Sorted L

摘要：注意因为堆中是链表节点，我们在初始化堆时还要新建一个的类。代码初始化大小为的堆拿出堆顶元素将堆顶元素的下一个加入堆中 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...

stefanieliang 2019-08-14 12:30 评论0 收藏0
LeetCode 之 JavaScript 解答第23题 —— 合并K个有序链表（Merge K S

摘要：分治算法递归每层操作分解将原问题分解成一系列的子问题。分治算法满足的条件可分解原问题与分解成的小问题具有相同的模式无关联原问题分解成的子问题可以独立求解，子问题之间没有相关性，这一点是分治算法跟动态规划的明显区别。 Time：2019/4/10Title: Merge K Sorted ListsDifficulty: DifficultyAuthor: 小鹿题目：Merge K...

zhou_you 2019-08-23 16:53 评论0 收藏0