Clone a Singly Linked List

Posted in

Clone a Singly Linked List
vinaykhatri

Vinay Khatri
Last updated on March 29, 2024

    You are given a singly linked list, having n nodes in it with each node having a pointer that is pointing to the succeeding node of the linked list. Your task is to clone the entire singly linked list and return a new copy of the given linked list.

    Example 1:

    Output: 1->2->3->4->5
    
    

    Explanation: The cloned linked list will contain the exact same nodes as the original linked list, in the same order. Hence, the nodes of the new linked list will be: 1->2->3->4->5. Example 2:

    Output: 0->1->2
    
    

    Explanation: The clone of the original linked list will be: 0->1->2

    Approach 1: Naive Approach

    The first approach is to take a new linked list having n nodes, where n is the number of nodes of the original linked list. Then, we need to copy the traversed nodes to the new linked list in the same order.

    Algorithm

    1. Create an empty linked list.
    2. Initialize two pointers, one pointer pointing to the head and the other one pointing to the tail.
    3. The tail pointer will point to the new linked list’s last node.
    4. Start traversing the original linked list.
    5. For every node n traversed in the original list, create a new node for the new list and set its data as the data of the n .
    6. Update the tail to point to the node next in the new list.
    7. Update the current pointer to point to the node next in the original list.

    The implementation of the aforementioned approach in C++, Java, and Python is shown below:

    C++

    #include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    using namespace std;
     
    // Structure to define a node
    // in the linked list
    // having an integer data,
    // and a pointer pointing to the next node.
    struct Node
    {
        int data;
        struct Node* next;
    };
     
    // Utility function that takes head 
    // of a linked list as its parameter
    // and prints the linked list.
    void printList(struct Node* head)
    {
        struct Node* ptr = head;
        while (ptr)
        {
            cout << ptr->data << "->";
            ptr = ptr->next;
        }
     
        cout << "null"; } // Utility function that pushes creates a node and // pushes it to the start of the linked list. void push(struct Node** head, int data) { // create a new node // and assign its value as the data struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data;
     
      // assign the newNode's next pointer
      // to point to the head of current first node of the original list.
        newNode->next = *head;
     
      // Update the head as the newNode, this way the it
      // will point to the first node of the list.
        *head = newNode;
    }
     
    // Function to clone the given linked list and
    // return the head of the new 
    // list, that is the copy of the original list.
    struct Node* copyList(struct Node* head)
    {
      // pointer to traverse the given linked list
        struct Node* current = head; 
    
      // create a new linked list
      struct Node* newList = NULL;  
    
        // tail pointer to point the new list's last node.
        struct Node* tail = NULL;      
     
        while (current != NULL)
        {
            // if the new list is empty
        // insert the first node
            if (newList == NULL)
            {
                newList = (struct Node*)malloc(sizeof(struct Node));
                newList->data = current->data;
                newList->next = NULL;
                tail = newList;
            }
            else {
                tail->next = (struct Node*)malloc(sizeof(struct Node));
                tail = tail->next;
                tail->data = current->data;
                tail->next = NULL;
            }
            current = current->next;
        }
     
        return newList;
    }
     
    int main(void)
    {
        // original linked list
        int lList[] = {1, 2, 3, 4};
        int n = sizeof(lList)/sizeof(lList[0]);
     
        // points to the head node of the linked list
        struct Node* head = NULL;
     
        // create a linked list
        for (int i = n-1; i >= 0; i--) {
            push(&head, lList[i]);
        }
     
        // cloned list
        struct Node* newList = copyList(head);
     
      // print the cloned new list
        printList(newList);
     
        return 0;
    }

    Output:

    Original list: 
    1-> 2-> 3-> 4-> null
    Cloned list: 
    1-> 2-> 3-> 4-> null

    Java

    // Class to define a node
    // in the linked list
    // having an integer data,
    // and a pointer to the next node.
    class Node
    {
        int data;
        Node next;
     
        Node(int data, Node next)
        {
            this.data = data;
            this.next = next;
        }
     
        Node() {}
    }
     
    class Main
    {
        // Utility function that takes head 
      // of a linked list as its parameter
      // and prints the linked list.
        public static void printList(Node head)
        {
            Node ptr = head;
            while (ptr != null)
            {
                System.out.print(ptr.data + " —> ");
                ptr = ptr.next;
            }
     
            System.out.println("null");
        }
     
      // Function to clone the given linked list and
      // return the head of the new 
      // list, that is the copy of the original list.
        public static Node copyList(Node head)
        {
        // pointer to traverse the given linked list
            Node current = head;    
    
        // create a new linked list
            Node newList = null;    
    
        // tail pointer to point to the new list's last node.
            Node tail = null;       
     
            while (current != null)
            {
                // if the new list is empty
          // insert the first node
                if (newList == null)
                {
                    newList = new Node(current.data, null);
                    tail = newList;
                }
                else {
                    tail.next = new Node();
                    tail = tail.next;
                    tail.data = current.data;
                    tail.next = null;
                }
                current = current.next;
            }
     
            return newList;
        }
     
        public static void main(String[] args)
        {
             // original linked list
            int[] lList = {1, 2, 3, 4};
     
            // points to the head node of the linked list
            Node head = null;
     
            // create a linked list
            for (int i = lList.length - 1; i >= 0; i--) {
                head = new Node(lList[i], head);
            }
     
             // cloned list
            Node newList = copyList(head);
     
        // print the original list
        System.out.println("Original list: ");
            printList(head);
    
            // print the cloned new list
        System.out.println("Cloned list: ");
            printList(newList);
        }
    }

    Output:

    Original list: 
    1-> 2-> 3-> 4-> null
    Cloned list: 
    1-> 2-> 3-> 4-> null

    Python

    # Class to define a node
    # in the linked list
    # having an integer data,
    # and a pointer to the next node.
    class Node:
        def __init__(self, data=None, next=None):
            self.data = data
            self.next = next
     
     
    # Utility function that takes head 
    # of a linked list as its parameter
    # and prints the linked list.
    def printList(head):
     
        ptr = head
        while ptr:
            print(ptr.data, end=" —> ")
            ptr = ptr.next
        print("null")
     
    # Function to clone the given linked list and
    # return the head of the new 
    # list, that is the copy of the original list.
    def copyList(head):
     
        # pointer to traverse the given linked list
        current = head     
    
        # create a new linked list
        newList = None      
    
        # tail pointer to point the new list's last node.
        tail = None        
     
        while current:
            # if the new list is empty
            # insert the first node
            if newList is None:
                newList = Node(current.data, None)
                tail = newList
            else:
                tail.next = Node()
                tail = tail.next
                tail.data = current.data
                tail.next = None
            current = current.next
     
        return newList
     
    if __name__ == '__main__':
    
        # construct a linked list
        head = None
        for i in reversed(range(4)):
            head = Node(i + 1, head)
    
        # cloned list
        newList = copyList(head)
        
        # print the original list
        print("Original list: ")
        printList(head)
    
        # print the cloned new list
        print("Cloned list: ")
        printList(newList)

    Output:

    Original list: 
    1-> 2-> 3-> 4-> null
    Cloned list: 
    1-> 2-> 3-> 4-> null

    Complexity Analysis

    Time complexity: The time complexity here is O(N), with N being the nodes present in the tree. This is because we are copying the nodes of one linked list in the other only once. However, in this approach, linking is getting repeated.

    Approach 2: Dummy Node Approach

    This approach, as the name suggests, includes a dummy node in the place of the head node to store the first node to which the tail pointer will point and the whole linked list gets copied.

    Al gorithm

    1. Create an empty linked list.
    2. Create a dummy node and point the first node to it.
    3. Insert a new node in a heap and set its data.
    4. Point the tail pointer to the dummy node and point the next node to the tail node.
    5. Print the new linked list.

    The implementation of this approach in C++, Java, and Python is as follows:

    C++

    #include <iostream>
    #include <stdio.h>
    #include <stddlib.h>
    using namespace std;
     
    // Structure to define a node
    // in the linked list
    // having an integer data,
    // and a pointer to the next node.
    struct Node
    {
        int data;
        struct Node* next;
    };
     
    // Utility function that takes head 
    // of a linked list as its parameter
    // and prints the linked list.
    void printList(struct Node* head)
    {
        struct Node* ptr = head;
        while (ptr)
        {
            cout << ptr->data << "-> ";
            ptr = ptr->next;
        }
     
        cout << "null"; } // Utility function that pushes creates a node and // inserts it to the start of the linked list. void push(struct Node** head, int data) { // create a new node // and assign its value as the data struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data;
     
        // assign the newNode's next pointer
        // to point to the head of the current first node of the original list.
        newNode->next = *head;
     
        // Update the head as the newNode, this way the it
        // will point to the first node of the list.
        *head = newNode;
    }
     
     
    // Function to clone the given linked list and
    // return the head of the new 
    // list, that is the copy of the original list.
    struct Node* copyList(struct Node* head)
    {
        // pointer to traverse the given linked list
        struct Node* current = head;    
    
        // create a new linked list
        struct Node* tail; 
    
        // create a new list              
        struct Node dummy;              
    
        dummy.next = NULL;
        
        // point the tail to the dummy node
        tail = &dummy;                  
     
        while (current != NULL)
        {
            // insert each traversed node 
            // of the original list to the tail
            push(&(tail->next), current->data);       
    
            // update the tail to point to
            // the next node og the new list
            tail = tail->next;          
            current = current->next;
        }
        return dummy.next;
    }
     
    int main(void)
    {
        // original linked list
        int lList[] = {1, 2, 3, 4};
        int n = sizeof(lList)/sizeof(lList[0]);
     
        // points to the head node of the linked list
        struct Node* head = NULL;
     
        // create a linked list
        for (int i = n-1; i >= 0; i--) {
            push(&head, lList[i]);
        }
     
        // cloned list
        struct Node* newList = copyList(head);
    
        // print the original list
        cout << "Original list: \n";
        printList(head);
     
        // print the cloned new list
        cout << "\nCloned list: \n";
        printList(newList);
     
        return 0;  
    }

    Output:

    Original list: 
    1-> 2-> 3-> 4-> null
    Cloned list: 
    1-> 2-> 3-> 4-> null

    Java

    // Class to define a node
    // in the linked list
    // having an integer data,
    // and a pointer to the next node.
    class Node
    {
        int data;
        Node next;
     
        Node(int data, Node next)
        {
            this.data = data;
            this.next = next;
        }
     
        Node() {}
    }
     
    class Main
    {
        // Utility function that takes head 
    	// of a linked list as its parameter
    	// and prints the linked list.
        public static void printList(Node head)
        {
            Node ptr = head;
            while (ptr != null)
            {
                System.out.print(ptr.data + " —> ");
                ptr = ptr.next;
            }
     
            System.out.println("null");
        }
     
    	// Function to clone the given linked list and
    	// return the head of the new 
    	// list, that is the copy of the original list.
        public static Node copyList(Node head)
        {
    		// pointer to traverse the given linked list
            Node current = head;        
    
    		// create a new linked list
            Node tail;                  
    
    		// create a new list        
            Node dummy = new Node();   
     
    		// point the tail to the dummy node
            tail = dummy;               
     
            while (current != null)
            {
                // insert each traversed node 
    			// of the original list to the tail
                tail.next = new Node(current.data, tail.next);
     
                // update the tail to point to
    			// the next node og the new list
                tail = tail.next;
                current = current.next;
            }
            return dummy.next;
        }
     
        public static void main(String[] args)
        {
                     // original linked list
            int[] lList = {1, 2, 3, 4};
     
            // points to the head node of the linked list
            Node head = null;
     
            // create a linked list
            for (int i = lList.length - 1; i >= 0; i--) {
                head = new Node(lList[i], head);
            }
     
             // cloned list
            Node newList = copyList(head);
     
    		// print the original list
    		System.out.println("Original list: ");
            printList(head);
    
            // print the cloned new list
    		System.out.println("Cloned list: ");
            printList(newList);
        }
    }

    Output:

    Original list: 
    1-> 2-> 3-> 4-> null
    Cloned list: 
    1-> 2-> 3-> 4-> null

    Python

    # Class to define a node
    # in the linked list
    # having an integer data,
    # and a pointer to the next node.
    class Node:
        def __init__(self, data=None, next=None):
            self.data = data
            self.next = next
     
    # Utility function that takes head 
    # of a linked list as its parameter
    # and prints the linked list.
    def printList(head):
     
        ptr = head
        while ptr:
            print(ptr.data, end=" —> ")
            ptr = ptr.next
     
        print("null")
     
    # Function to clone the given linked list and
    # return the head of the new 
    # list, that is the copy of the original list.
    def copyList(head):
     
        # pointer to traverse the given linked list
        current = head 
    
        # create a new list           
        dummy = Node()         
     
        # point the tail to the dummy node
        tail = dummy            
     
        while current:
            # insert each traversed node 
            # of the original list to the tail
            tail.next = Node(current.data, tail.next) 
    
            # update the tail to point to
            # the next node og the new list   
            tail = tail.next    
            current = current.next
     
        return dummy.next
     
     
    if __name__ == '__main__':
     
        # create a linked list
        head = None
        for i in reversed(range(4)):
            head = Node(i + 1, head)
     
        # cloned list
        newList = copyList(head)
    
        # print the original list
        print("Original list: ")
        printList(head)
     
        # print the cloned new list
        print("Cloned list: ")
        printList(newList)

    Output:

    Original list: 
    1-> 2-> 3-> 4-> null
    Cloned list: 
    1-> 2-> 3-> 4-> null

    Complexity Analysis

    Time complexity: The time complexity here is O(N), with N being the nodes present in the tree. This is so because we are using a dummy node in the place of the head node to store the first node to which the tail pointer will point

    Approach 3: Recursive Approach

    This approach is the most precise among all the approaches. This approach will copy the nodes of the original stack. However, it uses more space compared to other approaches.

    Al gorithm

    1. Create an empty linked list.
    2. Recursively copy the nodes of the original linked list in the new linked list.
    3. If the head of the linked list is equal to NULL, then return false, which means that the linked list does not contain any node.
    4. Insert a new node in a heap with the help of the `malloc()` function and set its data.
    5. Print the new linked list.

    The implementation of the approach in C++, Java, and Python is as follows:

    C++

    #include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    using namespace std;
    
    // Structure to define a node
    // in the linked list
    // having an integer data,
    // and a pointer to the next node.
    struct Node
    {
        int data;
        struct Node* next;
    };
     
    // Utility function that takes head 
    // of a linked list as its parameter
    // and prints the linked list.
    void printList(struct Node* head)
    {
        struct Node* ptr = head;
        while (ptr)
        {
            cout << ptr->data << "-> ";
            ptr = ptr->next;
        }
     
        cout << "null"; } // Utility function that pushes creates a node and // inserts it to the start of the linked list. void push(struct Node** head, int data) { // create a new node // and assign its value as the data struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data;
     
        // assign the newNode's next pointer
        // to point to the head of current first node of the original list.
        newNode->next = *head;
     
        // Update the head as the newNode, this way the it
        // will point to the first node of the list.
        *head = newNode;
    }
     
    // Recursive function to clone the given linked list and
    // return the head of the new 
    // list, that is the copy of the original list.
    struct Node* copyList(struct Node* head)
    {
        if (head == NULL) {
            return NULL;
        }
        else {
            // create a new node
            // and assign its value as the data
            struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
            newNode->data = head->data;
     
            // recursively assign the next pointer 
            // to the next nodes of current pointer
            newNode->next = copyList(head->next);
     
            return newNode;
        }
    }
     
    int main(void)
    {
        // original linked list
        int lList[] = {1, 2, 3, 4};
        int n = sizeof(lList)/sizeof(lList[0]);
     
        // points to the head node of the linked list
        struct Node* head = NULL;
     
        // create a linked list
        for (int i = n-1; i >= 0; i--) {
            push(&head, lList[i]);
        }
     
        // cloned list
        struct Node* newList = copyList(head);
    
        // print the original list
        cout << "Original list: \n";
        printList(head);
     
        // print the cloned new list
        cout << "\nCloned list: \n";
        printList(newList);
     
        return 0;
    }

    Output:

    Original list: 
    1-> 2-> 3-> 4-> null
    Cloned list: 
    1-> 2-> 3-> 4-> null

    Java

    // Class to define a node
    // in the linked list
    // having an integer data,
    // and a pointer to the next node.
    class Node
    {
        int data;
        Node next;
     
        Node(int data, Node next)
        {
            this.data = data;
            this.next = next;
        }
     
        Node(int data) {
            this(data, null);
        }
    }
     
    class Main
    {
         
    	// Utility function that takes head 
    	// of a linked list as its parameter
    	// and prints the linked list.
        public static void printList(Node head)
        {
            Node ptr = head;
            while (ptr != null)
            {
                System.out.print(ptr.data + " —> ");
                ptr = ptr.next;
            }
     
            System.out.println("null");
        }
     
    	// Recursive function to clone the given linked list and
    	// return the head of the new 
    	// list, that is the copy of the original list.
        public static Node copyList(Node head)
        {
            if (head == null) {
                return null;
            }
     
            // create a new node
    		// and assign its value as the data
            Node newNode = new Node(head.data);
     
           	// recursively assign the next pointer 
    		// to the next nodes of current pointer
            newNode.next = copyList(head.next);
     
            return newNode;
        }
     
        public static void main(String[] args)
        {
                             // original linked list
            int[] lList = {1, 2, 3, 4};
     
            // points to the head node of the linked list
            Node head = null;
     
            // create a linked list
            for (int i = lList.length - 1; i >= 0; i--) {
                head = new Node(lList[i], head);
            }
     
             // cloned list
            Node newList = copyList(head);
     
    		// print the original list
    		System.out.println("Original list: ");
            printList(head);
    
            // print the cloned new list
    		System.out.println("Cloned list: ");
            printList(newList);
    
        }
    }

    Output:

    Original list: 
    1-> 2-> 3-> 4-> null
    Cloned list: 
    1-> 2-> 3-> 4-> null

    Python

    # Class to define a node
    # in the linked list
    # having an integer data,
    # and a pointer to the next node.
    class Node:
        def __init__(self, data=None, next=None):
            self.data = data
            self.next = next
    # Utility function that takes head 
    # of a linked list as its parameter
    # and prints the linked list.
    def printList(head):
     
        ptr = head
        while ptr:
            print(ptr.data, end=" —> ")
            ptr = ptr.next
        print("null")
    
    # Recursive function to clone the given linked list and
    # return the head of the new 
    # list, that is the copy of the original list.
    def copyList(head):
     
        if head is None:
            return None
     
        # create a new node
    	# and assign its value as the data
        newNode = Node(head.data) 
        
    	# recursively assign the next pointer 
    	# to the next nodes of current pointer
        newNode.next = copyList(head.next)
     
        return newNode
     
    if __name__ == '__main__':
     
        # create a linked list
    	head = None
    	for i in reversed(range(4)):
    		head = Node(i + 1, head)
     
        # cloned list
    	newList = copyList(head)
    
    	# print the original list
    	print("Original list: ")
    	printList(head)
     
        # print the cloned new list
    	print("Cloned list: ")
    	printList(newList)

    Output:

    Original list: 
    1-> 2-> 3-> 4-> null
    Cloned list: 
    1-> 2-> 3-> 4-> null

    Complexity Analysis

    Time complexity: The time complexity of this approach is O(N), with N being the nodes present in the tree. This is because we are recursively copying the nodes and each node is getting traversed only once.

    Wrapping Up

    In this article, we have learned how to clone a singly linked list. We discussed three different approaches that allow us to clone a singly linked list. Each approach is explained with the help of code examples in the three popular programming languages, namely C++, Java, and Python. Also, the output of each code example is highlighted to help you understand each approach better.

    Happy Learning!

    People are also reading:

    Leave a Comment on this Post

    0 Comments