21. 合并两个有序链表

1. 题目描述

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

示例：

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

2. 解题思路

事实上，处理链表也就是在处理链表之间的指针的关系，这些指针就像是一条线一样，将所有的数据穿在一起，形成了一条链表。

我们只需要每次对两个链表的节点进行对比，然后让当前指针指向相对较小的数，然后将指针指向调整到指向的数的后面，这样依次对比完两个节点，就可以实现两个链表的有序合并。

需要注意的是，我们需要考虑链表长度不同的情况，由于两个链表都是有序链表，如果有一条链表遍历完了，另外一条链表没有遍历完，就直接将没遍历完的部分放在新链表最后就可以了。

3. 代码实现

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    // 定义新链表的头结点
    let head = new ListNode();
    // 当前指针指向的节点
    let cur = head;
    while (l1&&l2){
        if(l1.val<=l2.val){
            // 先指向只较小的节点 
            cur.next = l1
            // 在将指针的指向移动
            l1 = l1.next
        }else{
            cur.next = l2
            l2 = l2.next
        }
        // 连接好一个节点之后，指针的方向也会移动一位
        cur = cur.next
    }
    // 处理两个链表长度不同的情况
    cur.next = l1!==null?l1:l2
    // 返回最后的结果，头指针指向的那个位置，就代表新生成的链表
    return head.next
};

4. 提交结果