[LeetCode]21.合并两个有序链表

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

示例：

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

思路:

这是一道简单难度的题目。用伪头部节点技巧，判断l2->val是否大于链表1的游标指向的节点值cursor1->val且同时小于该节点子节点值cursor1->next->val。如果是，则将该节点插入这个位置，且 cursor1 前进一步，直到l1或l2到达末尾。如果l1到达尾部而l2没有到达尾部，则将l2剩下的部分全部连接到l1尾部即可，因为l1和l2均为有序链表。

AC代码:

/**
 * 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 == nullptr) 
        {
            if(l2 == nullptr) 
                return nullptr;
            else
                return l2;
        }
        else
        {
            if(l2 == nullptr) 
                return l1;
        }
        //l1 != nullptr, l2 != nullptr
        ListNode dummyHeadNode(-10000);
        dummyHeadNode.next = l1;
        ListNode* cursor1 = &dummyHeadNode,* cursor2 = l2;
        while(cursor1 != nullptr && cursor1->next != nullptr && cursor2 != nullptr)
        {
            if(cursor1->val <= cursor2->val && cursor1->next->val > cursor2->val)
            {
                ListNode* temp = cursor2;
                cursor2 = cursor2->next;
                temp->next = cursor1->next;
                cursor1->next = temp;
            }
            cursor1 = cursor1->next;
        }
        if(cursor1->next == nullptr && cursor2 != nullptr)
            cursor1->next = cursor2;
        return dummyHeadNode.next;
    }

};