[数据结构与算法]力扣：链表的合并

题目：将两个升序链表合并为一个新的?升序?链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

解法一：递归法

思路：首先判断两类特殊情况，l1或l2中有一个为空的情况，然后比较l1和l2的数值大小，若l1->data < l2->data,则l1->next为新的头结点，进行mergeLists(l1->next,l2)递归，反之同理。

class Solution {

public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

if(l1==NULL) {return l2;}

if(l2==NULL) {return l1;}

if(l1->val<l2->val) {

l1->next = mergeTwoLists(l1->next,l2);

return l1; }

else{ l2->next = mergeTwoLists(l1,l2->next);

return l2; }

}

};

解法二：迭代法

思路：创建一个新节点p,让q指向p，当l1,l2均不为空时，依次比较l1和l2val的值，较小的连到q的next，l1或l2向后移动，q向后移动，依次迭代。当其中一链表为空时，输入语句???q->next=(l1!=NULL)?l1:l2;

最后，函数返回p->next.

class?Solution?{

public:

????ListNode*?mergeTwoLists(ListNode*?l1,?ListNode*?l2)?{

??????????ListNode?*p?=?new?ListNode(0);

??????????ListNode?*q?=?p;

??????????while(l1!=NULL?&&?l2!=NULL){

??????????????if(l1->val<l2->val){

??????????????????q->next?=?l1;

?????????????????? ?l1=l1->next;

??????????????}

??????????????else{

??????????????????q->next?=?l2;

??????????????????l2=l2->next;

??????????????}

?????????????q?=?q->next

? }

??????q->next=(l1!=NULL)?l1:l2;

??????return?p->next;

????}

};