Я работаю над классом SinglyLinkedList на C++, где я поддерживаю указатели как на начало, так и на конец списка, а также целочисленный размер для отслеживания числа узлов. Моя цель — реализовать функцию replace(int x), которая заменяет каждое вхождение значения x в связанном списке на число узлов x, каждый из которых содержит значение 1 >. Например, если связанный список — 4 -> 5 -> 3 -> 8 -> 5 и я вызываю replace(3), ожидаемый результат должен быть 4 -> 5 -> 1 - > 1 -> 1 -> 8 -> 5. Кроме того, если значение x не отображается в списке, список должен остаться неизменным.
Интерфейс:
Код: Выделить всё
struct SinglyLinkedList
{
Node* head, * tail;
int size;
SinglyLinkedList() :head(nullptr), tail(nullptr), size(0) {}; // Default constructor
void replace(int X);
};
Моя попытка:
Код: Выделить всё
void SinglyLinkedList::replace(int X)
{
Node dummyHead(0, head);
Node* curr = head, * prev = &dummyHead;
while (curr)
{
if (curr->value == X)
{
Node* nextNode = curr->next;
for (int i = 0; i < X; i++)
{
prev->next = new Node(1);
size++;
prev = prev->next;
}
if (curr == tail)
{
tail = prev;
}
prev->next = nextNode;
curr = nextNode;
}
else
{
prev = curr;
curr = curr->next;
}
}
head = dummyHead.next;
}
Основная идея моего подхода заключается в том, чтобы пройти по связанному списку, сохраняя при этом указатели на текущий узел (curr) и предыдущий узел (prev). Когда я нахожу узел, содержащий значение x, я заменяю его, вставляя x новых узлов, каждый со значением 1. Я использую фиктивный заголовок, чтобы упростить логику вставки, особенно при обработке крайних случаев, таких как замена заголовка списка. После вставки новых узлов я правильно соединяю оставшуюся часть списка и гарантирую, что размер обновится соответствующим образом.
Поскольку я работаю над более крупным заданием в своем курсе «Структуры данных и алгоритмы», которое включает тесты, мне удалось определить, что проблема заключается в этой функции. Могу ли я получить помощь в определении проблемы? Есть ли что-то очевидное, что не сработает? Возможно, я не во всех случаях правильно обновляю хвост?
Подробнее здесь:
https://stackoverflow.com/questions/791 ... management
Мобильная версия