# Clone a Singly Linked List

Posted in  Vinay Khatri
Last updated on November 14, 2022

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
// 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.
{
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.

// Update the head as the newNode, this way the it
// will point to the first node of the list.
}

// Function to clone the given linked list and
// return the head of the new
// list, that is the copy of the original list.
{
// pointer to traverse the given linked list

// 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)
{
int lList[] = {1, 2, 3, 4};
int n = sizeof(lList)/sizeof(lList);

for (int i = n-1; i >= 0; i--) {
}

// cloned list

// 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
// 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.
{
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.
{
// pointer to traverse the given linked list

// 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)
{
int[] lList = {1, 2, 3, 4};

for (int i = lList.length - 1; i >= 0; i--) {
}

// cloned list

// print the original list
System.out.println("Original list: ");

// 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
# 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.

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.

# pointer to traverse the given linked list

# 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__':

for i in reversed(range(4)):

# cloned list

# print the original list
print("Original list: ")

# 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
// 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.
{
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.

// Update the head as the newNode, this way the it
// will point to the first node of the list.
}

// Function to clone the given linked list and
// return the head of the new
// list, that is the copy of the original list.
{
// pointer to traverse the given linked list

// 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)
{
int lList[] = {1, 2, 3, 4};
int n = sizeof(lList)/sizeof(lList);

for (int i = n-1; i >= 0; i--) {
}

// cloned list

// print the original list
cout << "Original list: \n";

// 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
// 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.
{
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.
{
// pointer to traverse the given linked list

// 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)
{
int[] lList = {1, 2, 3, 4};

for (int i = lList.length - 1; i >= 0; i--) {
}

// cloned list

// print the original list
System.out.println("Original list: ");

// 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
# 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.

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.

# pointer to traverse the given linked list

# 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__':

for i in reversed(range(4)):

# cloned list

# print the original list
print("Original list: ")

# 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
// 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.
{
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.

// Update the head as the newNode, this way the it
// will point to the first node of the list.
}

// Recursive function to clone the given linked list and
// return the head of the new
// list, that is the copy of the original list.
{
return NULL;
}
else {
// create a new node
// and assign its value as the data
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

// recursively assign the next pointer
// to the next nodes of current pointer

return newNode;
}
}

int main(void)
{
int lList[] = {1, 2, 3, 4};
int n = sizeof(lList)/sizeof(lList);

for (int i = n-1; i >= 0; i--) {
}

// cloned list

// print the original list
cout << "Original list: \n";

// 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
// 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.
{
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.
{
return null;
}

// create a new node
// and assign its value as the data

// recursively assign the next pointer
// to the next nodes of current pointer

return newNode;
}

public static void main(String[] args)
{
int[] lList = {1, 2, 3, 4};

for (int i = lList.length - 1; i >= 0; i--) {
}

// cloned list

// print the original list
System.out.println("Original list: ");

// 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
# 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.

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.

return None

# create a new node
# and assign its value as the data

# recursively assign the next pointer
# to the next nodes of current pointer

return newNode

if __name__ == '__main__':

for i in reversed(range(4)):

# cloned list

# print the original list
print("Original list: ")

# 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!