Advertisement
OIQ

Untitled

OIQ
Oct 9th, 2021
934
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.08 KB | None
  1. #include <iostream>
  2.  
  3. class LinkedList {
  4. private:
  5.     struct ListNode {
  6.         int value;
  7.         ListNode *next;
  8.     };
  9.  
  10. public:
  11.     ListNode *head, *tail;
  12.  
  13.     LinkedList();
  14.  
  15.     void add(int x);
  16.  
  17.     void print();
  18.  
  19.     ~LinkedList();
  20. };
  21.  
  22. LinkedList::LinkedList() {
  23.     this->head = nullptr;
  24.     this->tail = nullptr;
  25. }
  26.  
  27. LinkedList::~LinkedList() {
  28.     while (head) {
  29.         ListNode *head
  30.     }
  31. }
  32.  
  33. void LinkedList::add(int x) {
  34.     ListNode *node = new ListNode{x, nullptr};
  35.     if (!this->head) {
  36.         this->head = node;
  37.         this->tail = node;
  38.     } else {
  39.         this->tail->next = node;
  40.         this->tail = this->tail->next;
  41.     }
  42. }
  43.  
  44. void LinkedList::print() {
  45.     ListNode *current = head;
  46.     while (current) {
  47.         std::cout << current->value << " ";
  48.         current = current->next;
  49.     }
  50.     std::cout << "\n";
  51. }
  52.  
  53. LinkedList createList(int rest) {
  54.     LinkedList list;
  55.     for (int c, i = 0; i < rest; i++) {
  56.         std::cin >> c;
  57.         list.add(c);
  58.     }
  59.  
  60.     return list;
  61. }
  62.  
  63. LinkedList merge(const LinkedList &l1, const LinkedList &l2) {
  64.     LinkedList merged;
  65.     LinkedList tmp1 = l1;
  66.     LinkedList tmp2 = l2;
  67.  
  68.     while (tmp1.head || tmp2.head) {
  69.         if (tmp1.head && !tmp2.head) {
  70.             merged.add(tmp1.head->value);
  71.             tmp1.head = tmp1.head->next;
  72.         } else if (!tmp1.head && tmp2.head) {
  73.             merged.add(tmp2.head->value);
  74.             tmp2.head = tmp2.head->next;
  75.         } else if (tmp1.head && tmp2.head) {
  76.             if (tmp1.head->value > tmp2.head->value) {
  77.                 merged.add(tmp2.head->value);
  78.                 tmp2.head = tmp2.head->next;
  79.             } else {
  80.                 merged.add(tmp1.head->value);
  81.                 tmp1.head = tmp1.head->next;
  82.             }
  83.         } else {
  84.             break;
  85.         }
  86.     }
  87.  
  88.     return merged;
  89. }
  90.  
  91. int main() {
  92.     int n, m;
  93.     std::cin >> n >> m;
  94.  
  95.     LinkedList l1 = createList(n);
  96.     LinkedList l2 = createList(m);
  97.  
  98.     LinkedList merged_list = merge(l1, l2);
  99.     merged_list.print();
  100.  
  101.     return 0;
  102. }
  103.  
Advertisement
RAW Paste Data Copied
Advertisement