leetcode top100挑战, 每天不鸽一道题之 合并两个有序链表10/100)

leetcode top100挑战, 每天不鸽一道题之 合并两个有序链表10/100)

theme: cyanosis
highlight: atom-one-light

这是我参与更文挑战的第18天，活动详情查看： 更文挑战

题目描述

合并两个有序链表

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

leetcode-cn.com/problems/me…

// 示例1 
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
// 示例2 
输入：l1 = [], l2 = [0]
输出：[0]
复制代码

标签

递归

解题分析

1. 递归

直接上讲解。

直接使用递归可以轻松解决。
假设传入两个链表
[1,2,4], [1,3,4]

最需要注意的就是链表节点的值对比。

首先判断链表中的第一个节点，
因为是有序链表合并，让最小的节点排在最前面是正确的。
两个第一节点哪个小，就让哪个的next 等于递归函数的返回值。
这里递归函数传入的是之前第一节点对比后大的那个和小的下一个节点继续递归。
然后返回小的那个节点。

这里可能有点绕 看代码就行。
复制代码

来人上代码！！！！！

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    // 如果传入的链表不存在，那就返回第二个链表
    if(l1 === null) return l2 
    else if(l2 === null) return l1 
    //判断两个节点值，把小的节点返回，并且让小的节点下一个节点继续递归下去。
    else if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2)
        return l1 
    }
    //和上面的逻辑相同，永远返回小的节点并递归。
    else {
        l2.next = mergeTwoLists(l1, l2.next)
        return l2 
    }
};
复制代码

最后

从今天开始不鸽，每天一道算法题并发布文章，首先想要解决的题组为Top100，第十道题目打完收工！！