Clone a Singly Linked List

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:

• Minimum Edit Distance
• Union vs Structure
• The Stock Span Problem
• Python Data Structure
• Find maximum of minimum for every window size in a given array
• Matrix Multiplication in C
• Count all Possible Paths from Top Left to Bottom Right in a Matrix
• Array vs List
• Diameter of a Binary Tree
• Subset Sum Problem