合并两个有序链表

[Cosen95]

leetcode: https://leetcode-cn.com/problems/merge-two-sorted-lists/

[Cosen95]

题目分析

这道题目可以用迭代的方法来实现。当 l1 和l2都不是空链表时，判断 l1 和l2 哪一个链表的头节点的值更小，将较小值的节点添加到结果里，当一个节点被添加到结果里之后，将对应链表中的节点向后移一位。

在循环终止的时候， l1 和 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();
    let prev = head;
    while(l1 && l2) {
        if(l1.val <= l2.val) {
            prev.next = l1;
            l1 = l1.next
        } else {
            prev.next = l2;
            l2 = l2.next;
        }
        prev = prev.next
    }
    // 处理链表不等长的情况
    prev.next = l1 === null ? l2: l1
    // 返回起始结点
    return head.next
};