21.cc

struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
  ListNode *mergeTwoLists(ListNode *list1, ListNode *list2) {
    ListNode *dummy = new ListNode;
    ListNode *n = dummy;

    while (list1 && list2) {
      if (list1->val < list2->val) {
        n->next = list1;
        list1 = list1->next;
      } else {
        n->next = list2;
        list2 = list2->next;
      }
      n = n->next;
    }

    while (list1) {
      n->next = list1;
      list1 = list1->next;
      n = n->next;
    }

    while (list2) {
      n->next = list2;
      list2 = list2->next;
      n = n->next;
    }
    return dummy->next;
  }
};

int main() {}