Как клонировать связанный список?

Question

Вот основной пример связанного списка, который выглядит, как этот

головы - нет> [4] -> [6] -> [8] -> Ни

class Node: 

    def __init__(self, data, next = None): 
     self.data = data 
     self.next = next 

class LL: 

    def __init__(self): 
     self.head = None 

    def insert_tail(self, o): 
     new_node = Node(o) 
     if self.head == None: 
      self.head = new_node 
     else: 
      current = self.head 
      while current.next != None: 
       current = current.next 
      current.next = new_node 

    def __str__(self): 
     result = '' 
     current = self.head 
     while current != None: 
      result = result + str(current.data) + ", " 
      current = current.next 
     return result[:-2] 




    def clone(self, empty): 
     '''(LL, NoneType) -> LL 
     ''' 
     empty = LL() 
     current = self.head 
     while current != None: 
      empty.insert_tail(None) 
      current = current.next 
     return empty 

a = LL() 
a.insert_tail(4) 
a.insert_tail(6) 
a.insert_tail(8) 
print(a) 

Мой вопрос, как мог бы я клонировать это без какого-либо изменения исходного связанного списка? О, и я не хочу использовать какие-либо встроенные структуры данных для этого, так как ни в одном списке, словарях, кортежах и т. Д. (Импорт не импортируется)

EDIT: я не хочу клонировать данные, я просто хочу, связанный список, как:

голова [] -> [] -> [] -> None (Это будет клон один из приведенных выше)

Answer 1

Во-первых, список является неоптимальным. При реализации связанный список, вы должны:

1. элементов вставки в начале списка, что является O(1)
2. Если вы хотите поддержать вставки элементов в конце списка вы должны также следить за последний элемент список (таким образом, вставка будет O(1), а в вашем случае ее O(n)).

Для решения вашей проблемы вы можете воспользоваться следующим подходом: Создать пустой список и выполнить итерацию существующего. Для каждого элемента существующего списка просто добавьте его в конец нового списка.

Answer 2

Самый простой способ клонирования связанного списка состоит в том, чтобы ходить по списку, по элементам и создавать новый связанный список, когда вы вставляете новые элементы в хвост, как обычно. Создайте новый экземпляр класса LL, затем используйте метод insert_tail(), чтобы добавить элементы из списка, который вы клонируете.

Если вы надеетесь клонировать свой атрибут data, чтобы ваш клонированный список не взаимодействовал с оригиналом, вам придется использовать глубокое копирование в Python.

https://docs.python.org/2/library/copy.html

Стоит отметить, что это может быть просто проще использовать глубокую копию на весь связанный список, однако, ваш пробег может варьироваться в зависимости от того, что вы пытаетесь достичь.