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 

Tags:

related content