21. 合并两个有序链表

https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode/
https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/c-by-rush-2/
方法1：
/**
 * 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;
      //递归函数
       if (l1->val>l2->val)
       {
            l2->next=mergeTwoLists(l1,l2->next);
            return l2; 
       }
      else
      {
            l1->next=mergeTwoLists(l1->next,l2);
            return l1;
      }
    }
};

方法2：
/**
 * 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* p=new ListNode(0);//必须这么写
      ListNode*L=p;//必须这么写
      while (l1 && l2)
      {
        if (l1->val>l2->val)
        {
          p->next=l2;
          p=p->next;
          l2=l2->next;
        }
        else
        {
          p->next=l1;
          p=p->next;
          l1=l1->next;
        }
      }
      if (l1!=NULL)
        p->next=l1;
      if (l2!=NULL)
        p->next=l2;
    return L->next;
    }
};