题目

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

解决思路

关键在于l1和l2中分别存放的是两个单链表的首节点

function listNode(val) {
  this.val = val;
  this.next = null;
}

var mergeTwoLists = function(l1, l2) {
  // 将l2的每个节点值和l1节点值比较，将l2的节点复制为新的节点插入l1
  while (l2) {
    var prev = null;
    // cur中存入l1的首个节点
    var cur = l1;
    // 如果cur存在且l2首个节点的值大于l1的首个节点的值
    while (cur && l2.val > cur.val) {
      // 就把l1的首节点存到prev中，l1的第二个节点存到cur中
      prev = cur;
      cur = cur.next;
    }

    var newNode = new listNode(l2.val);
    // 将新节点指向l1的第二个节点
    newNode.next = cur;

    // 如果有prev，则将prev指向新节点；若没有，则新节点作为首个节点存入l1
    if (prev) {
      prev.next = newNode;
    } else {
      l1 = newNode;
    }
    // 将原来l2的下一个节点存入l2
    l2 = l2.next;
  }
  return l1;
}