Обратный двусвязный список путем замены данных
Учитывая двусвязный список, нас просят перевернуть список на месте, не используя дополнительное пространство.
Примеры:
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), так как мы не используем дополнительное пространство.