递归和双指针迭代：求解《21. 合并两个有序链表》和《剑指 Offer 25. 合并两个排序的链表》

var mergeTwoLists = function(l1, l2) {
  return l1 && l2 && {
    val: Math.min(l1.val, l2.val),
    next: l1.val < l2.val ? mergeTwoLists(l1.next, l2) : mergeTwoLists(l1, l2.next) 
  } || l1 || l2
};

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
  if l1 != nil && l2 != nil {
    if l1.Val < l2.Val {
      return &ListNode{
        Val: l1.Val,
        Next: mergeTwoLists(l1.Next, l2),
      }
    } else {
      return &ListNode{
        Val: l2.Val,
        Next: mergeTwoLists(l1, l2.Next),
      }
    }
  }
  if l1 != nil {
    return l1
  }
  if l2 != nil {
    return l2
  }
  return nil
}

class Solution {
  function mergeTwoLists($l1, $l2) {
    if ($l1 && $l2) {
      $node = new ListNode(min($l1->val, $l2->val));
      $node->next = $l1->val < $l2->val ? $this->mergeTwoLists($l1->next, $l2) : $this->mergeTwoLists($l1, $l2->next);
      return $node;
    }
    if ($l1) return $l1;
    if ($l2) return $l2;
  }
}

var mergeTwoLists = function(l1, l2) {
  const r = p = new ListNode(null)
  let p1 = l1, p2 = l2
  while (p1 || p2) {
    if (!p2 || p1 && p1.val < p2.val) {
      p.next = p1
      p1 = p1.next
    } else {
      p.next = p2
      p2 = p2.next
    }
    p = p.next
  }
  return r.next
};

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
  r, p1, p2 := &ListNode{}, l1, l2
  p := r
  for p1 != nil || p2 != nil {
    if p2 == nil || p1 != nil && p1.Val < p2.Val {
      p.Next = p1
      p1 = p1.Next
    } else {
      p.Next = p2
      p2 = p2.Next
    }
    p = p.Next
  }
  return r.Next
}

class Solution {
  function mergeTwoLists($l1, $l2) {
    $r = $p = new ListNode();
    $p1 = $l1;
    $p2 = $l2;
    while ($p1 || $p2) {
      if (!$p2 || $p1 && $p1->val < $p2->val) {
        $p->next = $p1;
        $p1 = $p1->next;
      } else {
        $p->next = $p2;
        $p2 = $p2->next;
      }
      $p = $p->next;
    }
    return $r->next;
  }
}