翻译

合并两个排好序的链表，并返回这个新链表。
新链表应该由这两个链表的头部拼接而成。

原文

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.

分析

这里我们使用递归的方法。我们构造一个新的ListNode，就叫做tmp，看着像是一个临时变量。的确，从局部来看它是临时变量，每次都会将l1或者l2赋值给它，但这里的l1和l2都是动态变化的，最重要的是每次return的tmp都是一个新的链表，最后一次返回的也就是我们所合并出来的链表。

我这里构造出来的链表顺序是由小到大的，因此当l1当前节点的值大于l2当前节点的值时，我们取的是l2这个较小的值，并将l2的下一个节点的值和l1当前节点的值放到下一次做对比，依次递归下去。

代码

C Plus Plus

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
  ListNode* mergeTwoLists(ListNode *l1, ListNode *l2) {
    if (l1 == NULL) return l2;
    if (l2 == NULL) return l1;

    if (l1->val > l2->val) {
      ListNode *tmp = l2;
      tmp->next = mergeTwoLists(l1, l2->next);
      return tmp;
    } else {
      ListNode *tmp = l1;
      tmp->next = mergeTwoLists(l1->next, l2);
      return tmp;
    }
  }
};

Java

update at 2016/09/17

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val > l2.val) {
            ListNode tmp = l2;
            tmp.next = mergeTwoLists(l1, l2.next);
            return tmp;
        } else {
            ListNode tmp = l1;
            tmp.next = mergeTwoLists(l1.next, l2);
            return tmp;
        }
    }
}