1、递归（4ms,93%;14.4MB,76%)

 1     //递归需关注目前这一层的数据如何处理，以及如何结束递归
 2     //即该层数据以什么状态传给下一层，以及数据以什么状态返回上一层
 3     ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
 4         //如果list1空了，则把剩下的list2返回给上一层接上链表
 5         if(list1==NULL)
 6         return list2;
 7         //如果list2空了，则把剩下的list1返回给上一层接上链表
 8         if(list2==NULL)
 9         return list1;
10         //此处list1的值小，则把list1后面的和list2一起打包给后面的人做
11         //你就想象后面的人有能力把打包的数据排序好后返回给你
12         if(list1->val<=list2->val){
13             list1->next=mergeTwoLists(list1->next,list2);
14             return list1;
15         }
16         //此处list2的值小，则把list2后面的和list1打包给后面的人做
17         else{
18             list2->next=mergeTwoLists(list1,list2->next);
19             return list2;
20         }
21     }

2、迭代（8ms,65%;14.2MB,98%）

 1  ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
 2         //指针head用于指向新生成的链表头结点
 3         ListNode *head=new ListNode();
 4         //指针temp相当于一根针，把两个链表串起来
 5         ListNode *temp=head;
 6         while(list1!=NULL&&list2!=NULL){
 7             if(list1->val<=list2->val){
 8                 //用temp把偏小的list1串起来
 9                 temp->next=list1;
10                 //list1移动到下一位方便比较后面的数据
11                 list1=list1->next;
12             }
13             else{
14                 temp->next=list2;
15                 list2=list2->next;
16             }
17             //temp必须保持在针头的位置方便串链表
18             temp=temp->next;
19         }
20         temp->next=list1==NULL? list2:list1;
21         return head->next;
22     }