美文网首页
lettcode#21 合并两个有序链表

lettcode#21 合并两个有序链表

作者: leeehao | 来源:发表于2020-07-16 12:23 被阅读0次

审题

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

题目解析

两个集合按照从小到大排序合并为一个集合,集合实现方式为链表,题目较为简单,主要考察链表操作。大家可以对自己要求 1 编过。

第一次

暴力解决,遍历 -> 比较 -> 插入 看起来代码蛮长其实没有太多含量,所以想一想有没有更好的方式?

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) return null;
        if (l1 == null && l2 != null) return l2;
        if (l1 != null && l2 == null) return l1;

        // init root node
        ListNode root = new ListNode();
        if (l1.val > l2.val) {
            root.val = l2.val;
            l2 = l2.next;
        } else {
            root.val = l1.val;
            l1 = l1.next;
        }

        // 遍历 -> 检查 -> 添加
        ListNode index = root;
        while(l1 != null && l2 != null) {
            ListNode node = new ListNode();
            if (l1.val < l2.val) {
                node.val = l1.val;
                l1 = l1.next;
            } else {
                node.val = l2.val;
                l2 = l2.next;
            }
            index.next = node;
            index = node;
        }
        
        // 补全
        ListNode l = l1 != null ? l1 : l2;
        while(l != null) {
            ListNode node = new ListNode();
            node.val = l.val;
            l = l.next;
            index.next = node;
            index = node;
        }

        return root;
    }
}

第二次

想一想链表天生适合递归,其实就是每次比较两个单节点的大小。

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) return null;
        if (l1 == null && l2 != null) return l2;
        if (l1 != null && l2 == null) return l1;

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

        return root;
    }
}

第三次

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) return null;
        if (l1 == null && l2 != null) return l2;
        if (l1 != null && l2 == null) return l1;

        if (l1.val > l2.val) {
            ListNode t = l1;
            l1 = l2;
            l2 = t;
        }
        ListNode root = l1;
        root.next = mergeTwoLists(l1.next, l2);

        return root;
    }
}

相关文章

  • leecode刷题(23)-- 合并两个有序链表

    leecode刷题(23)-- 合并两个有序链表 合并两个有序链表 将两个有序链表合并为一个新的有序链表并返回。新...

  • lettcode#21 合并两个有序链表

    审题 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 题目解析 ...

  • 合并单链表

    合并两个有序链表非递归实现 合并两个有序链表递归实现

  • leetcode 链表 [C语言]

    21. 合并两个有序链表 合并两个有序链表 61. 旋转链表 (快慢指针) 61. 旋转链表 相关标签 : 链表 ...

  • ARTS-Week6 有序链表合并、DevOps、Json解析、

    Algorithm LeetCode原题链接: 合并两个有序链表 将两个有序链表合并为一个新的有序链表并返回。新链...

  • 2018-12-26

    问题列表 合并两个有序链表 合并K个排序链表 合并区间 插入区间 问题与反馈 总结与收获 多个有序链表的合并,类似...

  • leetcode的题目21

    合并两个有序链表 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示...

  • Swift 合并两个有序链表 - LeetCode

    题目: 合并两个有序链表 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组...

  • LeetCode 21. 合并两个有序链表

    21. 合并两个有序链表 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成...

  • 刷leetCode算法题+解析(四)

    合并两个有序链表 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示...

网友评论

      本文标题:lettcode#21 合并两个有序链表

      本文链接:https://www.haomeiwen.com/subject/fulphktx.html