合并两个有序链表

[pwstrick]

/*
 *  合并两个链表
 */
function Merge(head1, head2) {
  if (head1 == null)
    return head2;
  if (head2 == null)
    return head1;
  var cur1 = head1.next,       //遍历 head1 的指针 
     cur2 = head2.next,       //遍历 head2 的指针
    head = null,        //合并后链表的头结点
    cur = null;         //合并后的链表在尾结点
  //合并后链表的头结点为第一个结点元素最小的那个链表的头结点
  if (cur1.data > cur2.data) {
    head = head2;
    cur = cur2;
    cur2 = cur2.next;
  } else {
    head = head1;
    cur = cur1;
    cur1 = cur1.next;
  } 
  //每次找链表剩余结点的最小值对应的结点连接到合并后链表的尾部 
  while (cur1 && cur2) {
    if (cur1.data < cur2.data) {
      cur.next = cur1;
      cur = cur1;
      cur1 = cur1.next;
    } else {
      cur.next = cur2;
      cur = cur2;
      cur2 = cur2.next;
    }
  }
  //当遍历完一个链表后把另外一个链表剩余的结点链接到合并后的链表后面
  if (cur1 != null) {
    cur.next = cur1;
  }
  if (cur2 != null) {
    cur.next = cur2;
  }
  return head;
}