leetCode (js)：21. 合并两个有序链表

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

示例：

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

    /**
   * 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) {
          let rear = new ListNode();
          let current_reference = rear;
1      while (l1 && l2) {
2         if(l1.val <= l2.val){
3             current_reference.next = new ListNode(l1.val);
4             l1 = l1.next;
5         } else {
6             current_reference.next = new ListNode(l2.val);
7             l2 = l2.next;
8         }
9         current_reference = current_reference.next;
10      }
11       current_reference.next = l1 || l2;
12       return rear.next; 
      };

      先说一下思路合并俩个单链表采用尾插法。这里传入的l1、 l2 指的是俩个linklist对应的指向第一个节点的引用新建l3置空表。rear（尾指针/尾引用）初值为l3，且始终指向l3表尾复制一份rear给current_reference,我们操作时只操作current_reference，rear当作最后返回即可。虽说rear总指向结尾但此时l3为空所以rear指向null。
      当代码执行到行1处，判断l1 l2俩个引用是否已经把俩个linklist查询完毕，如果l1查询结束此时值为null（l2同理）。行2是正常的判断逻辑如果这样难理解，可以换个思路比如c中的 l1 -> val即可。行3是将l3的rear指向l1的1（即l3第一个值为l1的1）。行4是将原本指向l1第一个节点的引用指向l1的第二个节点（即l1.next）。行6、7与行3、4大意相同。行9是将l3原本指向l3中空引用节点rear（{'val':undefined,'next':null}）指向第一个节点（{'val':1, 'next':null}）。行11是将l1与l2中剩余的节点放入l3中。行12是返回指向l3第一个节点的引用。

l1 ：1 2 4
l2 ：1 3 4
l3 ：1 1 2 3 4 4

while：round 1
行234执行前l1指向1，l2指向1，l3指向null，cur = {'val':undefined,'next':null}
行234执行后l1指向2，l2指向1，l3指向1，cur = {'val':1,'next':null}

while：round 2
行567执行前l1指向2，l2指向1，l3指向1，cur = {'val':1,'next':null}
行567执行后l1指向2，l2指向3，l3指向1(l2的1)，cur = {'val':1,'next':null}

...

其他步骤类似与上面的分析直到l1查询到最后一个节点 l1->next = nullwhile循环结束此时l2中还剩节点4，通过行11将节点4插入l3尾部即可。

思考：上面的分析都是我从c的角度出发按照下图中的单链表数据结构来解释，那么从js的角度如何来实现这种数据结构？

不带头节点的单链表

// 1-2-4 1-3-4 => 1-1-2-3-4-4
var l1 = {
     'val': 1,
     'next': {
       'val': 2,
       'next': {
         'val': 4,
         'next': null
       }
     }
   },
   l2 = {
         'val': 1,
         'next': {
           'val': 3,
           'next': {
             'val': 4,
             'next': null
           }
         }
       };

这样就是从逻辑上实现了单链表。把l1&l2传入mergeTwoLists得到结果如下：

合并后的l3单链表

同结果 1-1-2-3-4-4 相同，所以通过结果也验证了js实现单链表结构也正是如上代码段所示。

其实通过l1&l2的结构可以发现这种结构很像树。由此可以引出单链表转换二叉树的问题。