合并有序链表

ListNode *mergeTwoLists(ListNode *list1, ListNode *list2) {
    // 设置虚拟头节点
    ListNode dummy(0);
    // 每一轮从两个链表中选出较小的，连接到头节点后面
    ListNode *cur = &dummy;
    while (list1 != nullptr && list2 != nullptr) {
        if (list1->val <= list2->val) {
            cur->next = list1;
            list1 = list1->next;
        } else {
            cur->next = list2;
            list2 = list2->next;
        }
        // 注意，每一轮 cur 要往后挪动
        cur = cur->next;
    }
    // 任意一个链表空了，那么连接另一个链表
    if (list1 == nullptr) {
        cur->next = list2;
    } else if (list2 == nullptr) {
        cur->next = list1;
    }
    return dummy.next;
}