21 LeetCode 合并两给有序链表 《C语言》《完整分析 加 代码》

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

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

思想：
首先，看到这给题目，我想信大多数同学都是想着直接把两给链表合并成一个链表，但是如果你仔细看到，它不仅仅是直接合并，而且是按照谁小谁在前面，所以，我们要认真思考这个问题。
第一步：我们应该创建一个新的头节点，把上面两给链表联系在一起。
第二部： 我们还要比较两个链表里面值《val》的大小，并且把值小的放在前面；
第三步： 还要考虑，当一个链表如果已近到NULL了，而另外一个链表还没有为NULL，那么是不是应该将不为NULL的链表继续放在新创的链表后面，直到另外一个也为NULL，这样才能完整的结束；

下面我们就看一下执行代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
  if(l1 == NULL && l2 == NULL)
      return NULL;
    if(l1 == NULL)
        return l2;
    if(l2 == NULL)
        return l1;
    struct ListNode* head;   
    struct ListNode* p;
    if(l1->val < l2->val)
    {
        head = p = l1;
        l1 = l1->next; 
    }
    else
    {
        head = p = l2;
        l2 = l2->next; 
    }
     while(l1 && l2)
     {
         if(l1->val < l2->val)
         {
             p->next = l1;
             l1 = l1->next;
         }
         else
         {
             p->next = l2;
             l2 = l2->next;
         }
         p = p->next;
     }
    if(l1 == NULL)
    {
        p->next = l2;
    }
    else
    {
        p->next = l1;
    }
    return head;
}

当然，我试了一下，如果把 《== NULL 直接用 ( ! )代替，时间可以提高到4ms左右》我知道这不是最优解答。如果，还有更优的解答，希望。有大佬告诉我。