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.

 

to see which companies asked this question

 

表示有点难，想了很久。

递归的算法：

1,3,10,12

2,3,4,7,9,11

递归的算法就是，首先，首节点1和2进行比较，1比2小，所以3再和2比较，因为2比3小，所以2被加入，3和3比较。（我之前想错了，不应该是两两比较，应该是较大的和较小的剩下的比较）

/** * 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;        ListNode *ret = NULL;        if (l1->val < l2->val)    {        ret = l1;        ret->next = mergeTwoLists(l1->next, l2);    }    else    {        ret = l2;        ret->next = mergeTwoLists(l1, l2->next);    }        return ret;}};