错题3 LeetCode C语言 合并两个有序链表

合并两个有序链表

自信满满地以为这是道水题，写完代码测试样例也通过了，可是还是WA了。
向超级奈斯的助教老哥求救之后终于明白了，能出问题的地方太多了，我这是写了个什么破程序。
具体原因应该是我想的方法不太好实现，要考虑的东西太多（其实就是too young too simple）。

（好比题目要你组装一辆车拉货物，小车的组装顺序组装方法你都清楚，但当实际组装完成，开始拉货的时候，指不定哪个部分在拉什么货的时候会产生故障。）

以后写这类型的题不要插入了，还是建一个新链表8。

废话不多说，上题。

题目

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

示例：

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

WRONG ANSWER

思路：
①游标指针p指向l1的结点，游标指针q指向l2的结点。
②游动指针p，找到合适的位置，把此时q指向的结点插入到l1中。
③r指向[p指向的结点]的上一个结点，s在 [q指向的结点] 加入l1 （意味着q->next不再指向l2中的下一个结点而是指向l1中的下一个结点） 之前保存l2中下一个结点的位置。

缺陷：
①定义的指针太多，容易绕晕，循环结束条件不好找。
②对于这道题而言，这个逻辑还不够简单。
③。。。

代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {

    struct ListNode *p,*q,*r,*s;
    int temp;
    p=l1;
    q=l2;
    r=l1;
    if(p==NULL) return l2;
    else if(q==NULL) return l1;
    else while(q!=NULL){
        while(q->val >= p->val){
            if(p->next==NULL)
                 break;
            r=p;
            p=p->next;
        }
        r->next=q;
        s=q->next;
        q->next=p;
        p=q;
        q=s;
    }
    return l1;
}

ACCEPTED

思路：
构建个新链表，然后不停比较 l1 l2 中最小的元素，把比较小的添加到新链表上，直至 l1或l2元素已经全部添加到新链表中，最后把没全添加完的链表剩下的一段直接全接到新链表上。

优点：
①逻辑简单。
②需定义的指针只有三个。
③循环终止条件非常清楚明了。

代码：

/**
 * 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 dummy(-1);
        ListNode *p=&dummy;
        for(;l1!=NULL && l2!=NULL;p=p->next)
        {
            if(l1->val > l2->val)
            {
                p->next=l2;
                l2=l2->next;
            }
            else 
            {
                p->next=l1;
                l1=l1->next;
            }
        }
        if(l1==NULL)
            p->next=l2;
        else 
            p->next=l1;
        return dummy.next;
    }
};