Можем ли мы перевернуть элементы в одноцикловом связанном списке, используя только два указателя? Возможно ли это, эффективно и какова временная сложность?
Мне нужно четко знать только одну вещь, поскольку я пробовал обращение одинарного циклического связанного списка с использованием языка C. В этом я не могу найти правильный путь и понятия не имею об этом. Может ли кто-нибудь помочь мне правильно и кратко рассказать о временной сложности и, наконец, нельзя ли повернуть вспять, не объявляя NULL?
struct node *Reversescll(struct node *head) {
if (head == NULL) {
head->next = head;
return head;
}
struct node *back = NULL;
struct node *c = head;
struct node *next = NULL;
do {
next = c->next;
c->next = back;
back = c;
c = next;
} while (c != head);
head->next = back;
head = back;
return head;
}
Да, да, в некоторой степени (поскольку связанные списки по своей сути неэффективны), O(n).
if (head==NULL) { head->next==head; хорошо не закончится.
Тебе не хватает ; после while(c!=head)
См. medium.com/@acharya.piyush224/… для ознакомления с рекурсивным алгоритмом обратного списка. он использует только один указатель на итерацию.
Пожалуйста, научитесь правильно форматировать код. Это очень важно. С нечитаемым кодом сложно работать, особенно новичкам. Я сделал это для тебя.
Действительно ли актуальна часть заголовка «использование только двух указателей»? Я собирался спросить, как вы считаете, но потом увидел, что код в вопросе использует более двух в любом способе счета.
Ответы 1
Ваш подход почти правильный, но у вас проблема с пустым списком: вам нужно просто вернуть head или NULL, а не разыменовывать head->next, когда head равно NULL.
Вот исправленная версия:
struct node *Reversescll(struct node *head) {
if (head == NULL || head->next == head)
return head;
struct node *back = NULL;
struct node *c = head;
do {
struct node *next = c->next;
c->next = back;
back = c;
c = next;
} while (c != head);
head->next = back;
return head;
}
Обратите внимание, что функция всегда возвращает свой аргумент.
Теперь, чтобы полностью ответить на ваш вопрос:
Можем ли мы перевернуть элементы в одноцикловом связанном списке, используя только два указателя?
Да, это можно сделать, используя всего два дополнительных указателя в дополнение к аргументу head (в приведенном выше коде используются 3 дополнительных указателя):
struct node *Reversescll(struct node *head) {
if (head == NULL)
return head;
struct node *back = NULL;
while (head->next) {
struct node *next = head->next;
head->next = back;
back = head;
head = next;
}
head->next = back;
return head;
}
Эффективно ли это и какова временная сложность?
Он эффективен, а сложность линейна, O(n). Это оптимально, поскольку необходимо менять каждый узел.
Порядок слов в ОП странный, но я думаю, что они говорят, что у них есть круговой (односвязный) список. Если да, то ваш цикл while (head->next) не завершится.
@JohnBollinger: Я позволю себе не согласиться, поскольку указатель next начального узла будет установлен на начальное значение back, а именно на нулевой указатель, цикл остановится, когда он снова достигнет этого узла, если список действительно является циклическим. Если список не является циклическим, классический код в первой версии выше приведет к сбою при достижении нулевого указателя, тогда как этот код остановится на последнем узле, свяжет его с предыдущим и вернет его. IOW код переворачивает список независимо от того, является ли он циклическим или нет. Первичный тест head->next == head даже не нужен.
Мои извинения. Кажется, я только что выскочил из альтернативной вселенной, где ты этого не делал. Я знаю это, потому что искал что-то в этом роде, прежде чем комментировать. +1 тогда. Не обращайте на меня внимания.
Вы хотели что-то поместить в спойлер?