21. 合并两个有序链表

该很简单，但是如何写的优雅呢？

这是leetcode给出的默认代码

/**
 * 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) {
        
    }
};

• 我们可以看到返回值是ListNode*，那么我们最好要创建一个新的链表来存储两个链表的值。因为先存储再排序很麻烦，我们直接来实现每当插入一个数的时候，进行一个判断。这样，直接return 新链表的节点就可以了

• /**
   * 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) {
          ListNode *mix = new ListNode(0);
          ListNode *cur = mix;
          while(l1&&l2)
          {
              if(l1->val<l2->val)//当l1的值小于l2的节点值得时候，把l1插入新链表
              {
                  cur->next = l1;
                  l1=l1->next;
              } else//否则，插入l2 得节点值
              {
                  cur->next =l2;
                  l2 = l2->next;
              }
              cur = cur->next;//每次插入后，把节点指向下一个空间
          }
          cur->next = l1?l1:l2;//如果l1，l2有一个被读完了，就会跳出循环
          //那么，剩下的所有节点都插入到新的链表当中去
          //就是说，如果cur->next = l1 的话，
          return mix->next;
      }
  
  };
  

• 当然，这个解法存在内存泄露的缺点。