7-1 两个有序链表序列的合并 (20 分)

给定两个有序链表，请将它们合并为一个有序链表。

方法：比较两个链表的头节点的值，将较小的节点的值作为新链表的头节点，并将该节点从原链表中删除。重复上述步骤，直到两个链表都为空。最后，如果仍有剩余的链表，将它们接到新链表的末尾。

代码实现：

/**
 * 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 *dummy = new ListNode(-1), *cur = dummy;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                cur->next = l1;
                l1 = l1->next;
            } else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        cur->next = l1 ? l1 : l2;
        return dummy->next;
    }
};