21.合并两个有序链表

思路1 循环遍历两个链表，把符合条件的加在新建的链表节点后面，最后返回新的链表

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode* res; ListNode* p1=l1; ListNode* p2=l2; ListNode* p; if(l1==NULL){return l2;} if(l2==NULL){return l1;} if(p1->val>p2->val) { res=p2; p2=p2->next; } else { res=p1; p1=p1->next; } p=res; while(p1!=NULL&&p2!=NULL){ if(p1->val>p2->val) { p->next=p2; p2=p2->next; } else { p->next=p1; p1=p1->next; } p=p->next; } if(p1!=NULL){p->next=p1;} if(p2!=NULL){p->next=p2;} return res; }

时间复杂度是O（n+m） n和m分别是两个链表的长度 复杂度较高，效果不好 思路2 看了题解之后，修改成了递归的思路来做 首先找最开头的节点，然后每次循环的时候都把val值小的时候接在这个节点后面，一直到有一个为null的时候，把另一个接在后面。

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