Обратный двусвязный список путем замены данных

Опубликовано: 27 Февраля, 2023

Учитывая двусвязный список, нас просят перевернуть список на месте, не используя дополнительное пространство.

Примеры:

Input : 1 <--> 2 <--> 5 <--> 6 <--> 7
Output : 7 <--> 6 <--> 5 <--> 2 <--> 1

Input : 11 <--> 22 <--> 33 <--> 22 <--> 1
Output : 1 <--> 22 <--> 33 <--> 22 <--> 11 

Мы обсудили три метода реверсирования двусвязного списка: реверсирование двусвязного списка, реверсирование двусвязного списка (набор 2) и реверсирование двусвязного списка с использованием рекурсии.
Первые два метода работают за время O(n) и не требуют дополнительного места. Первый метод работает путем замены следующего и предыдущего указателей каждого узла. Второй метод берет каждый узел из списка и добавляет его в начало списка.
Есть и другой подход, более интуитивный, но и более затратный.
Этот метод аналогичен обратному массиву. Чтобы перевернуть массив, мы помещаем два указателя — один в начало, а другой в конец списка. Затем мы меняем местами данные двух указателей и продвигаем оба указателя друг к другу. Мы останавливаемся либо при встрече двух указателей, либо при их пересечении. Мы выполняем ровно n/2 свопов, а временная сложность также O(N).
Двусвязный список имеет указатель как на предыдущий, так и на следующий, что означает, что мы можем перемещаться по списку как в прямом, так и в обратном направлении. Итак, если мы поместим указатель (скажем, левый указатель) в начало списка, а другой правый указатель — в конец списка, мы сможем перемещать эти указатели друг к другу, перемещая левый указатель и удаляя правый указатель.

Алгоритм:

Step 1: Set LEFT to head of list
Step 2: Traverse the list and set RIGHT to end of the list 
Step 3: Repeat following steps while LEFT != RIGHT and 
        LEFT->PREV != RIGHT
Step 4: Swap LEFT->DATA and RIGHT->DATA
Step 5: Advance LEFT pointer by one, LEFT = LEFT->NEXT
Step 6: Recede RIGHT pointer by one, i.e RIGHT = RIGHT->PREV
        [END OF LOOP]
Step 7: End

Примечание о сравнительной эффективности трех методов

Необходимо упомянуть несколько вещей. Этот метод прост в реализации, но он также более затратен по сравнению с методом обмена указателями. Это потому, что мы обмениваем данные, а не указатели. Замена данных может быть более дорогостоящей, если узлы представляют собой большие сложные типы данных с несколькими элементами данных. Напротив, указатель на узел всегда будет иметь более простой тип данных и иметь размер 4 или 8 байт.

Ниже приведена реализация алгоритма.

Временная сложность: O(n) , так как мы используем цикл для прохождения n раз. Где n — количество узлов в связанном списке.
Вспомогательное пространство: O(1), так как мы не используем дополнительное пространство.

РЕКОМЕНДУЕМЫЕ СТАТЬИ