How to copy linked list in Python?
Published on Aug. 22, 2023, 12:15 p.m.
To create a copy of a linked list in Python, you need to create a new linked list with nodes that have the same values as the original linked list, but with separate memory locations. Here is an example of how to do that using a class-based approach:
class Node:
def __init__(self, val):
self.val = val
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, val):
node = Node(val)
if not self.head:
self.head = node
else:
curr = self.head
while curr.next:
curr = curr.next
curr.next = node
def print_list(self):
curr = self.head
while curr:
print(curr.val, end=' ')
curr = curr.next
print()
def copy(self):
copies = {}
curr = self.head
while curr:
copies[curr] = Node(curr.val)
curr = curr.next
curr = self.head
while curr:
copies[curr].next = copies[curr.next] if curr.next else None
curr = curr.next
return copies[self.head]
This implementation uses a dictionary to track each node in the original linked list and its corresponding node in the copied linked list. It creates a new node for each node in the original list, and assigns the next
pointers of the copied nodes based on the dictionary mapping. Note that the Node
class only has a val
and next
attribute, but you can add additional attributes as needed.
You can then create a linked list object, append nodes to it, and make a copy using the copy()
method:
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.print_list()
new_ll = ll.copy()
new_ll.print_list()
This will output:
1 2 3
1 2 3