1. 首页
  2. Leetcode经典148题

leetCode-21-Merge-Two-Sorted-Lists

题目描述(简单难度)

leetCode-21-Merge-Two-Sorted-Lists

合并两个有序链表。

解法一 迭代

遍历两个链表。

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode h = new ListNode(0);
    ListNode ans=h;
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            h.next = l1;
            h = h.next;
            l1 = l1.next;
        } else {
            h.next = l2;
            h = h.next;
            l2 = l2.next;
        }
    }
    if(l1==null){
        h.next=l2;
    }
    if(l2==null){
        h.next=l1;
    } 
    return ans.next;
}

时间复杂度:O(m + n)。

空间复杂度:O(1)。

解法二 递归

参考[这里](Merge Two Sorted Lists)

ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if(l1 == null) return l2;
    if(l2 == null) return l1;

    if(l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l2.next, l1);
        return l2;
    }
}

时间复杂度:

空间复杂度:

递归看起来,两个字,优雅!但是关于递归的时间复杂度,空间复杂度的求法,先留个坑吧。

作者:windliang

来源:https://windliang.cc

JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:leetCode-21-Merge-Two-Sorted-Lists

链接:https://www.javajike.com/article/3158.html

« leetCode-20-Valid Parentheses
leetCode-22-Generate-Parentheses»

相关推荐

QR code