/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        //创建新的链表
        ListNode *p=new ListNode(0);//创建p节点作为头节点
        ListNode *cur=p;//创建指针指向p（初始）节点

        while(l1!=NULL&&l2!=NULL)
        {
               if(l1->val<l2->val) 
            {
                cur->next=l1;
                l1=l1->next;//直接等于l1即可，即移动l1指针，如果等于l1->val就改变了l1的值
            } 
                 else//不用else if（l1->val>l2->val）是因为会漏下两者相等的情况
            {
                cur->next=l2;
                l2=l2->next;
            }

            cur=cur->next;
        }
        if(l1!=NULL) // 当其中一个链表遍历完后，直接连接剩下的链表
            {
                cur->next=l1;
            }
            else
            {
                cur->next=l2;
            }
        return p->next;

    }
};