21. Merge Two Sorted List

---恢复内容开始---

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.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

合并两个有序链表，最后返回新的链表。实现思路很简单，对比两个链表每一个结点值的大小，然后优先拼接到新表的尾部。

1.非递归方法:

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     struct ListNode *next;
 6  * };
 7  */
 8 struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
 9     if(l1 == NULL) return l2;
10     if(l2 == NULL) return l1;
11     if(l1==NULL && l2==NULL) return NULL;
12     struct ListNode *head=NULL;
13     if(l1->val < l2->val)
14     {
15         head=l1;
16         l1=l1->next;
17     }
18     else
19     {
20         head=l2;
21         l2=l2->next;
22     }
23     struct ListNode *p=head; 
24     while(l1 && l2)
25     {
26         if(l1->val < l2->val)
27         {
28             p->next=l1;
29             l1=l1->next;
30         }
31         else
32         {
33            p->next=l2;
34            l2=l2->next;
35         }
36         p=p->next;
37     }
38  
39     if(l1) p->next=l1;  //如果还剩下l1结点，则把l1加到新链表
40     if(l2) p->next=l2;  //如果还剩下l2结点，则把l2加到新链表
41     return head;
42 }

2.递归方法。这个方法还是看别的大神做的，代码很简洁，很惊艳。

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     struct ListNode *next;
 6  * };
 7  */
 8 struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
 9     if(l1 == NULL) return l2;
10     if(l2 == NULL) return l1;
11     if(l1==NULL && l2==NULL) return NULL;
12     //假如一开始是l1数据域小，递归结束后返回新l1(即首地址),反之同理。
13     if(l1->val <= l2->val){
14         l1->next = mergeTwoLists(l1->next,l2);
15         return l1;
16     }else{
17         l2->next = mergeTwoLists(l1,l2->next);
18         return l2;
19     }
20 }