Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <stdlib.h>
- using namespace std;
- struct Node
- {
- int value;
- Node* next;
- };
- Node* addnode(int value, Node* next);
- Node* mergesort(Node* head);
- Node* merge(Node* head_one, Node* head_two);
- Node* addnode(int number, Node* next)
- {
- Node* tnode = new Node;
- tnode->value = number;
- tnode->next = next;
- return tnode;
- }
- Node* merge(Node* head_one, Node* head_two)
- {
- Node* head_three = nullptr;
- if (head_one == nullptr)
- {
- return head_two;
- }
- if (head_two == nullptr)
- {
- return head_one;
- }
- if (head_one->value < head_two->value)
- {
- head_three = head_one;
- head_three->next = merge(head_one->next, head_two);
- }
- else
- {
- head_three = head_two;
- head_three->next = merge(head_one, head_two->next);
- }
- return head_three;
- }
- Node* mergesort(Node* head)
- {
- Node* head_one;
- Node* head_two;
- if ((head == nullptr) || (head->next == nullptr))
- {
- return head;
- }
- head_one = head;
- head_two = head->next;
- while ((head_two != nullptr) && (head_two->next != nullptr))
- {
- head = head->next;
- head_two = head_two->next->next;
- }
- head_two = head->next;
- head->next = nullptr;
- return merge(mergesort(head_one), mergesort(head_two));
- }
- Node* Reverse(Node * head)
- {
- Node* temp = head; // текущий узел
- Node* prev = nullptr; // предыдущий узел
- Node* nexto; // следующий узел
- while (temp != nullptr)
- {
- nexto = temp->next; // 250 (запоминаем значение слеующего узла) для того чтобы разрушить связь
- if (nexto == nullptr)
- {
- head = temp;
- }
- temp->next = prev; //разрушали связь между узлами, (разворачиваем узлы) где было 250 сейчас nullptr
- prev = temp; // на след. итерации пред узлом будет текущий
- temp = nexto; // переходим на след итерацию
- }
- return head;
- // head_.next = prev; или
- }
- int main()
- {
- Node* head;
- Node* current;
- Node* next;
- int test[] = { 1,3,2,7,6 };
- head = nullptr;
- for (int i = 0; i < 5; ++i)
- {
- head = addnode(test[i], head);
- }
- head = mergesort(head);
- head = Reverse(head);
- head = mergesort(head);
- int i = 0;
- for (current = head; current != nullptr; current = current->next)
- {
- cout << test[i++] << " " << current->value << endl;
- }
- for (current = head; current != nullptr; current = next)
- {
- next = current->next;
- delete current;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
