【JS每日一算法】16. 合并两个有序链表(递归法、迭代法)

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

更多JS版本题解点击链接关注该仓库👀

/**
 * @description: 递归法  TC:O(m+n)  SC:O(m+n)
 * @author: JunLiangWang
 * @param {*} list1  有序链表1
 * @param {*} list2  有序链表2
 * @return {*}
 */
function recursion(list1,list2)
{
    if(!list1)return list2
    if(!list2)return list1
    if(list1.val<list2.val)
    {
        list1.next=recursion(list1.next,list2)
        return list1
    }
    else
    {
        list2.next=recursion(list1,list2.next)
        return list2
    }
}


/**
 * @description: 迭代法   TC:O(m+n)  SC:O(1)
 * @author: JunLiangWang
 * @param {*} list1  有序链表1
 * @param {*} list2  有序链表2
 * @return {*}
 */
function iteration(list1,list2)
{
    const head=new ListNode(-1)
    let prev=head
    while(list1&&list2)
    {
        if(list1.val<list2.val)
        {
            prev.next=list1
            list1=list1.next
        }
        else
        {
            prev.next=list2
            list2=list2.next
        }
        prev=prev.next
    }
    prev.next=list1?list1:list2
    return head.next
}