LeetCode腾讯精选练习50题-21.合并两个有序链表

LeetCode腾讯精选练习50题-21.合并两个有序链表,第1张

目录
      • 题目描述
      • 解题思路
      • 代码(Java)

题目描述
  • 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
example
input  : l1 = [1,2,4], l2 = [1,3,4]
output : [1,1,2,3,4,4]
input  : l1 = [], l2 = []
output : []
input  : l1 = [], l2 = [0]
output : [0]
解题思路

思路1

  • 先把最简单的情况排除,一个链表为空时直接返回另一个链表即可

  • 同时遍历两个链表,比较节点值的大小

  • 将较小的节点放到结果链表中,并将值较小的节点的指针后移,另一个链表指针不移动

  • 继续上述 *** 作,直至两个链表指针至少一个为null

  • 将剩下的那部分非空的链表节点整体放到结果链表的最后

  • 时间复杂度O(m + n)

  • 空间复杂度O(1)

思路2

  • 把思路1的内容转化成递归写法
  • 退出边界就是一个为空时直接返回另一个链表
  • 时间复杂度O(m + n)
  • 空间复杂度O(m + n)
代码(Java)

思路1代码

public class Solution1 {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        ListNode list = new ListNode(-1);
        ListNode res = list;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                res.next = list1;
                list1 = list1.next;
            } else {
                res.next = list2;
                list2 = list2.next;
            }
            res = res.next;
        }
        // res.next = list1 != null ? list1 : list2;
        if (list1 != null) {
            res.next = list1;
        }
        if (list2 != null) {
            res.next = list2;
        }
        return list.next;
    }
}

思路2代码

public class Solution2 {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/868599.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-05-13
下一篇 2022-05-13

发表评论

登录后才能评论

评论列表(0条)

保存