合并两个有序链表（简单） yinshibanxian

一、题目描述

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

限制

0 <= 链表长度 <= 1000

二、题目解析

1. 遍历两个有序链表

   既然l1和l2均为有序链表，那么我们可以遍历这两个链表，并且创建一个哑节点作为新链表的前一个节点。

   • 当l1和l2均不为空时
     • 若l1.val < l2.val，以l1.val创建新链表的下一个节点，同时l1指向下一个节点
     • 反之，以l2.val创建新链表的下一个节点，同时l2指向下一个节点
   • 当l1不为空时,以l1.val创建新链表的下一个节点，同时l1指向下一个节点
   • 当l2不为空时,以l2.val创建新链表的下一个节点，同时l2指向下一个节点
   • 最后返回哑节点的下一个节点即可

    /**
    * Definition for singly-linked list.
    * function ListNode(val) {
    *     this.val = val;
    *     this.next = null;
    * }
    */
    /**
    * @param {ListNode} l1
    * @param {ListNode} l2
    * @return {ListNode}
    */
    var mergeTwoLists = function(l1, l2) {
        const head = new ListNode(null);
        let current = head;
        while(l1 != null || l2 != null) {
            if(l1 != null && l2 != null) {
                if(l1.val <  l2.val) {
                    current.next = new ListNode(l1.val);
                    l1 = l1.next;
                } else {
                    current.next = new ListNode(l2.val);
                    l2 = l2.next;
                }
            } else if(l1 != null) {
                current.next = new ListNode(l1.val);
                l1 = l1.next;
            } else if(l2 != null) {
                current.next = new ListNode(l2.val);
                l2 = l2.next;
            }
            current = current.next;
        }
        return head.next;
    };
   

   • 时间复杂度: O(M+N),M,N分别为l1,l2的长度
   • 空间复杂度: O(1),节点引用仅需要常数级别的空间大小

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof