LeetCode题解：21. 合并两个有序链表，迭代（优化），JavaScript，详细注释

[chencl1986]

原题链接：https://leetcode-cn.com/problems/merge-two-sorted-lists/

解题思路：

实现思路参考了官方题解。

1. 用双指针同时遍历两个链表。
2. l1.val<l2.val时，将l1存入新链表，l1向前移动一位
3. l2.val<l1.val时，将l2存入新链表，l2向前移动一位
4. l1.val=l2.val时，将l1和l2分别存入新链表，l1和l2都向前移动一位
5. 任意一个链表完成遍历之后，退出循环。
6. 此时另一个链表中的节点必然大于新链表且有序，只需要将新链表与剩下链表的节点链接即可。

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function (l1, l2) {
  // 创建一个伪节点，排序后的新链表的首节点会存储在dummyNode.next中
  let dummyNode = new ListNode(-1);
  // 存储新链表的节点，会随着新链表的连接而重新赋值
  // 新链表的首节点存储为dummyNode，避免在存储新链表时，首节点为空的问题
  let newListNode = dummyNode;

  // 当两个链表都有节点时，才进行遍历。
  // 当一个链表遍历完成之后，只需要将另一个链表连接在新链表之后即可
  while (l1 && l2) {
    // 对比两个节点的值大小，将值小的节点连接到新链表中
    if (l1.val <= l2.val) {
      newListNode.next = l1;
      l1 = l1.next;
    } else {
      newListNode.next = l2;
      l2 = l2.next;
    }
    newListNode = newListNode.next;
  }

  // 退出循环时，直接把还有节点的链表连接到新链表上。
  newListNode.next = l1 ? l1 : l2;

  // dummyNode.next指向的是新链表的第一个节点
  // 因此此处返回的就是新链表。
  return dummyNode.next;
};