text: // Problem Link:
  // https://leetcode.com/problems/merge-two-sorted-lists/
  
  // TC: O(n+m)
  // SC: O(1)
  
  #include <bits/stdc++.h>
  using namespace std;
  
  #define ll long long
  #define deb(x) cout << #x << ": " << x << "\n"
  
  class ListNode
  {
  public:
      int val;
      ListNode *next;
  
      ListNode() {}
      ListNode(int value) : val{value}, next{NULL} {}
  };
  
  void displayList(ListNode *head)
  {
      ListNode *curr = head;
      while (curr)
      {
          cout << curr->val << " ";
          curr = curr->next;
      }
  }
  
  ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
  {
      ListNode *head = new ListNode();
      ListNode *tail = head;
  
      while (l1 and l2)
      {
          if (l1->val < l2->val)
          {
              tail->next = l1;
              l1 = l1->next;
          }
          else
          {
              tail->next = l2;
              l2 = l2->next;
          }
          tail = tail->next;
      }
  
      tail->next = (l1 ? l1 : l2);
  
      return head->next;
  }
  
  void solve()
  {
      vector<int> nums1{1, 2, 4};
      vector<int> nums2{1, 3, 4};
  
      ListNode *head1 = new ListNode(nums1[0]);
      ListNode *curr = head1;
      for (int i = 1; i < nums1.size(); ++i)
      {
          curr->next = new ListNode(nums1[i]);
          curr = curr->next;
      }
  
      ListNode *head2 = new ListNode(nums2[0]);
      curr = head2;
      for (int i = 1; i < nums1.size(); ++i)
      {
          curr->next = new ListNode(nums2[i]);
          curr = curr->next;
      }
  
      displayList(head1);
      cout << endl;
  
      displayList(head2);
      cout << endl;
  
      ListNode *res = mergeTwoLists(head1, head2);
  
      displayList(res);
      cout << endl;
  }
  
  int main()
  {
      ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
      int t{1};
      // cin >> t;
      while (t--)
          solve();
      return 0;
  }