Учитывая одноциклический связанный список, мы должны разделить его на две равные половины. Если количество узлов в данном списке нечетное, то в первом списке будет на один узел больше, чем во втором списке.
Input : { 2, 3, 18, 25, 5 }
Output List 1 : { 2, 3, 18 }
Output List 2 : { 25, 5 }
Из приведенного выше рис. сначала мы должны найти средний узел данного кругового связанного списка.
Средний узел можно найти с помощью slow_ptr
и fast_ptr
. slow_ptr
увеличивается на один узел, тогда как fast_ptr
увеличивается на два узла. Когда fast_ptr->next == head
или fast_pr->next->next == head
, то нет приращения fast_ptr
или slow_ptr
и slow_ptr
в среднем узле списка.
Node *find_middle_node()
{
//slow pointer advances by 1
Node *slow_ptr = head;
//fast pointer advances by 2
Node *fast_ptr = head;
//If odd number of nodes then fast_ptr->next = head
//If even number of nodes then fast_ptr->next->next = head
while(fast_ptr->next != head && fast_ptr->next->next != head)
{
fast_ptr = fast_ptr->next->next;
slow_ptr = slow_ptr->next;
}
return slow_ptr;
}
После получения среднего узла узел, следующий за средним узлом, является главой второго списка вывода. Затем хвосты списков обновляются, так что круговой список сохраняется.
void split_list(circular_linked_list<T>& second_half)
{
Node *tail = find_tail_node();
Node *mid = find_middle_node();
second_half.head = mid->next;
tail->next = second_half.head;
mid->next = head;
}
Реализация С++ для разделения кругового связанного списка
#include <iostream>
#include <utility>
template <class T>
class circular_linked_list
{
struct Node
{
T data;
Node * next;
Node(T&& value) : data(std::move(value)), next(nullptr) {}
};
Node *head;
public:
circular_linked_list() : head(nullptr) {}
//copy constructor
circular_linked_list(const circular_linked_list& cll) = delete;
//move constructor
circular_linked_list(circular_linked_list&& cll) = delete;
//copy assignment
circular_linked_list& operator=(const circular_linked_list& cll) = delete;
//move assignment
circular_linked_list& operator=(circular_linked_list&& cll) = delete;
~circular_linked_list();
void insert_node(T&&);
void split_list(circular_linked_list<T>&);
void print_list();
private:
Node *find_tail_node()
{
Node *tmp = head;
while(tmp->next != head)
{
tmp = tmp->next;
}
return tmp;
}
Node *find_middle_node()
{
//slow pointer advances by 1
Node *slow_ptr = head;
//fast pointer advances by 2
Node *fast_ptr = head;
//If odd number of nodes then fast_ptr->next = head
//If even number of nodes then fast_ptr->next->next = head
while(fast_ptr->next != head && fast_ptr->next->next != head)
{
fast_ptr = fast_ptr->next->next;
slow_ptr = slow_ptr->next;
}
return slow_ptr;
}
};
template <class T>
void circular_linked_list<T>::insert_node(T&& value)
{
Node *node = new Node(std::move(value));
if(head == nullptr)
{
node->next = node;
head = node;
return;
}
Node *tmp = head;
while(tmp->next != head)
{
tmp = tmp->next;
}
tmp->next = node;
node->next = head;
}
template <class T>
void circular_linked_list<T>::split_list(circular_linked_list<T>& second_half)
{
Node *tail = find_tail_node();
Node *mid = find_middle_node();
second_half.head = mid->next;
tail->next = second_half.head;
mid->next = head;
}
template <class T>
void circular_linked_list<T>::print_list()
{
Node *tmp = head;
while(tmp->next != head)
{
std::cout << tmp->data << ' ';
tmp = tmp->next;
}
std::cout << tmp->data << '\n';
}
template <class T>
circular_linked_list<T>::~circular_linked_list()
{
Node *tmp = nullptr;
Node *tail = head;
while(tail->next != head)
{
tail = tail->next;
}
tail->next = nullptr;
while(head != nullptr)
{
tmp = head;
head = head->next;
delete tmp;
}
}
int main()
{
circular_linked_list<int> original_list;
original_list.insert_node(2);
original_list.insert_node(3);
original_list.insert_node(4);
original_list.insert_node(1);
original_list.insert_node(0);
std::cout << "The original list is : ";
original_list.print_list();
circular_linked_list<int> second_half;
original_list.split_list(second_half);
//Original list becomes first half
std::cout << "The first half : ";
original_list.print_list();
std::cout << "The second half : ";
second_half.print_list();
}
Посмотреть этот код на Github
Ссылка:
Введение в алгоритмы
Руководство по проектированию алгоритмов
Простые структуры данных и алгоритмы
Вам также может понравиться
Переместить все нечетные числа после четных в односвязный список
Объединить два отсортированных связанных списка (на месте)
Двойной циклический связанный список
Обратить связанный список< br /> Нахождение длины цикла в связном списке
Двусвязный список
Односвязный список
Следите за мной в Facebook и Twitter
Первоначально опубликовано на https://programmercave0.github.io 4 февраля 2018 г.