Есть ли алгоритм O (nlog (n)) для инвертирования простого связанного списка?

Question

В комментариях к this answer приведена идея, что преобразование простого связанного списка может быть выполнено только в O (nlog (n)), а не в O (n) времени.

Это определенно неверно - инверсия O (n) не является проблемой - просто пройдите по списку и измените указатели, когда вы идете. Требуются три временных указателя - это постоянная дополнительная память.

Я полностью понимаю, что O (nlog (n)) хуже (медленнее), чем O (n).

Но из любопытства - что может быть алгоритмом O (nlog (n)) для инверсии просто связанного списка? Предпочтительным является алгоритм с постоянной дополнительной памятью.

Answer 1

Я думаю, вы смущены. Вы говорите O (n log (n)), что на самом деле хуже, чем O (n). Возможно, вы имеете в виду O (log n)? Если это так, ответ - нет. Вы не можете инвертировать связанный список в O (log n). O (n) тривиально (и очевидное решение). O (n log (n)) не имеет большого смысла.

Редактировать: Итак, вы имеете в виду O (n log (n)). Тогда ответ «да». Как? Легко. Вы сортируете:

1. Подсчитайте длину списка. Стоимость: O (n);
2. Создайте массив такого же размера;
3. Скопируйте элементы связанного списка в массив в случайный заказ, положив первоначальный заказ как часть элемента. Например: [A, B, C] -> [(B, 2), (C, 3), (A, 1)]. Стоимость: O (n);
4. Сортируйте массив, используя эффективную сортировку (например, быструю сортировку) в инвертированном исходном порядке, например [(C, 3), (B, 2), (A, 1)]. Стоимость: O (n log (n));
5. Создайте связанный список из реверсивного массива. Стоимость: O (n).

Общая стоимость: O (п журнал (п))

Несмотря на все промежуточные этапы, вид является наиболее дорогостоящей операцией. Остальные шаги O (n) являются постоянными (это означает, что количество шагов не является коэффициентом n), поэтому общая стоимость равна O (n log (n)).

Редактировать 2: Я изначально не поместил элементы списка в произвольном порядке, но понял, что вы можете утверждать, что эффективный сортировка по уже отсортированному списку была меньше O (n log (n)), даже если вы реверсировали его. Теперь я не полностью убежден, что это так, но вышеупомянутая редакция устраняет эту потенциальную критику.

И да, это патологический вопрос (и ответ). Конечно, вы можете сделать это в O (n).

Answer 2

Ну ...

Вы можете использовать рекурсию, который принимает связанный список и инвертирует его, позвонив по телефону себя две половины связанного списка, где, если вход только два узла, он переворачивает их.

Это очень неэффективно, но я считаю, что это O (nlog (n)) ...

Что-то вроде следующего в псевдокоде (если у вас есть len функция, которая возвращает длину списка в O (N) и sub_list(list, start_id, end_id) функцию, которая возвращает подмножество списка, начиная с START_ID и заканчивая end_id в O (N)):

function invert(list) 

    if len(list) == 1 return list 

    if len(list) == 2: 
     new_list = list.next 
     new_list.next = list 
     return new_list 

    middle_of_list = len(list)/2 <-- integer division 

    first_half = invert (sub_list(list, 1, middle_of_list)) 
    second_half = invert (sub_list(list, middle_of_list+2, len(list)) 

    first_half.next = second_half 

    return first_half 

Answer 3

Каждый алгоритм O (n) также является O (n log n), поэтому ответ да.

Answer 4

Тупой идея, но О (п войти п), а не О (п)

• Присвоить каждый элемент списка уникальный ID. Идентификатор каждого преемника должен быть больше идентификатора элемента (O (n))
• Сортировка элементов по возрастанию с использованием ключа id как ключа с использованием любого алгоритма сортировки на основе сравнения (O (n log n))
• Создайте новый список, используя, выдаваемой сортировка элементов (O (N))

Answer 5

Если вы педантичным, то этот алгоритм O (N журнал N), так как указатели имеют размер не менее log n и должны быть назначены n раз.

Но на самом деле машины имеют фиксированный размер слова, поэтому это обычно не принимается во внимание.

Answer 6

Если вопрос действительно для алгоритма Ω (nlgn), возможно, этот чрезмерно сложный алгоритм будет делать?

• построить сбалансированное дерево структуры из связанного списка
• каждый лист содержит как исходное значение из связанного списка и номер индекса значения в связанном списке; использовать индекс как дерево ключа
• траверс дерева, чтобы сообщить все листья в порядке, обратном первоначальному индексу
• создать новый связанный список из сопоставления значений