Posted on by Kalkicode
Code Recursion

# Copy linked list using recursion

In this problem, we aim to copy a linked list using recursion. We need to design a program that creates a new linked list with the same data as the original linked list, while maintaining the recursive approach.

## Problem Statement

Given a linked list, our goal is to create a new linked list that is a copy of the original linked list, using a recursive approach.

## Example Scenario

Consider a linked list with the following elements:

``1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL``

We want to create a new linked list that is a copy of the original linked list using recursion.

## Idea to Solve the Problem

We can solve this problem using a recursive approach. During the traversal of the original linked list, we create a new node for each element and connect it to the new linked list. The recursive approach ensures that we traverse the entire original linked list and create a copy of it.

## Pseudocode

``````// Function to clone a linked list node recursively
{
if (node == NULL)
{
return NULL;
}
// Create new node
// Connect with next node
auxiliary->next = clones(node->next);
// Return new node
return auxiliary;
}

// Function to clone the entire linked list recursively
{
// Recursively clone the next nodes
// Find the last node
while (auxiliary != NULL && auxiliary->next != NULL)
{
auxiliary = auxiliary->next;
}
// Set tail node
colon->tail = auxiliary;
return colon;
}``````

## Algorithm Explanation

1. Create a function `clones` that takes a node as an argument.
2. If the given node is `NULL`, return `NULL`.
3. Create a new node using the data from the given node and recursively call `clones` on the next node.
4. Connect the newly created node with the returned cloned next node.
5. Return the newly created node.
6. Create a function `cloneLinkList` that takes the original linked list as an argument.
7. Create a new linked list using `newLinkedList`.
8. Clone the entire linked list using the `clones` function and set it as the head of the new linked list.
9. Find the last node of the new linked list.
10. Set the tail of the new linked list.
11. Return the new linked list.

## Code Solution

``````// C program for
// Copy linked list using recursion
#include <stdio.h>

#include <stdlib.h>

{
int data;
};
struct SingleLL
{
};
// Returns the new linked list
{
// Create memory of head and tail Nodes
struct SingleLL *sll = (struct SingleLL *) malloc(sizeof(struct SingleLL));
if (sll == NULL)
{
printf("Memory overflow\n");
}
else
{
sll->tail = NULL;
}
return sll;
}
// Returns the new node of linked list
{
// Create dynamic node
if (node == NULL)
{
}
else
{
// Set initial node value
node->data = data;
node->next = NULL;
}
return node;
}
void addNode(struct SingleLL *sll, int data)
{
{
}
else
{
// Append the node at last position
sll->tail->next = node;
}
sll->tail = node;
}
void display(struct SingleLL *sll)
{
{
return;
}
while (temp != NULL)
{
printf(" %d →", temp->data);
// Visit to next node
temp = temp->next;
}
printf(" NULL\n");
}
// This is cloning the linked list node using recursive
{
if (node == NULL)
{
return NULL;
}
// Create new node
// Connect with next node
auxiliary->next = clones(node->next);
// Return new node
return auxiliary;
}
{
// Recursively clone the next nodes
// Get the first node of clone linked list
// Find last node
while (auxiliary != NULL && auxiliary->next != NULL)
{
auxiliary = auxiliary->next;
}
// Set tail node
colon->tail = auxiliary;
return colon;
}
int main(int argc, char const *argv[])
{
//  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
printf("\n Before colon  ");
printf("\n Actual Linked List  : ");
display(actual);
printf("\n After colon  ");
printf("\n Colon Linked List  : ");
display(colon);
printf("\n After add new element   ");
printf("\n Colon Linked List  : ");
display(colon);
printf("\n Actual Linked List  : ");
display(actual);
return 0;
}``````

#### input

`````` Before colon
Actual Linked List  :  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL

After colon
Colon Linked List  :  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL

Colon Linked List  :  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 10 → NULL

Actual Linked List  :  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL``````
``````/*
Java Program for
*/
{
public int data;
{
this.data = data;
this.next = null;
}
}
public class SingleLL
{
public SingleLL()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
public void display()
{
{
return;
}
while (temp != null)
{
System.out.print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
System.out.println(" NULL");
}
// This is cloning the linked list node using recursive
{
if (node == null)
{
return null;
}
// Create new node
// Connect with next node
auxiliary.next = clones(node.next);
// Return new node
return auxiliary;
}
{
SingleLL colon = new SingleLL();
// Recursively clone the next nodes
// Get the first node of clone linked list
// Find last node
while (auxiliary != null && auxiliary.next != null)
{
auxiliary = auxiliary.next;
}
// Set tail node
colon.tail = auxiliary;
return colon;
}
public static void main(String[] args)
{
SingleLL actual = new SingleLL();
//  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
System.out.print("\n Before colon ");
actual.display();
System.out.print("\n After colon ");
colon.display();
System.out.print("\n After add new element ");
colon.display();
System.out.print("\n Actual Linked List : ");
actual.display();
}
}``````

#### input

`````` Before colon
Actual Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL

After colon
Colon Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL

Colon Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 10 → NULL

Actual Linked List :  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL``````
``````// Include header file
#include <iostream>
using namespace std;

/*
C++ Program for
*/

{
public:
int data;
{
this->data = data;
this->next = NULL;
}
};
class SingleLL
{
public:
SingleLL()
{
this->tail = NULL;
}
{
{
}
else
{
// Append the node at last position
this->tail->next = node;
}
this->tail = node;
}
void display()
{
{
cout << "\n Empty linked list" << endl;
return;
}
while (temp != NULL)
{
cout << " " << temp->data << " →";
// Visit to next node
temp = temp->next;
}
cout << " NULL" << endl;
}
// This is cloning the linked list node using recursive
{
if (node == NULL)
{
return NULL;
}
// Create new node
// Connect with next node
auxiliary->next = this->clones(node->next);
// Return new node
return auxiliary;
}
{
SingleLL *colon = new SingleLL();
// Recursively clone the next nodes
// Get the first node of clone linked list
// Find last node
while (auxiliary != NULL && auxiliary->next != NULL)
{
auxiliary = auxiliary->next;
}
// Set tail node
colon->tail = auxiliary;
return colon;
}
};
int main()
{
SingleLL *actual = new SingleLL();
//  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
cout << "\n Before colon ";
cout << "\n Actual Linked List :";
actual->display();
cout << "\n After colon ";
cout << "\n Colon Linked List :";
colon->display();
cout << "\n After add new element ";
cout << "\n Colon Linked List :";
colon->display();
cout << "\n Actual Linked List : ";
actual->display();
return 0;
}``````

#### input

`````` Before colon
Actual Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL

After colon
Colon Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL

Colon Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 10 → NULL

Actual Linked List :  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL``````
``````/*
Java Program for
*/
{
public int data;
{
this.data = data;
this.next = null;
}
}
public class SingleLL
{
public SingleLL()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
public void display()
{
{
return;
}
while (temp != null)
{
System.out.print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
System.out.println(" NULL");
}
// This is cloning the linked list node using recursive
{
if (node == null)
{
return null;
}
// Create new node
// Connect with next node
auxiliary.next = clones(node.next);
// Return new node
return auxiliary;
}
{
SingleLL colon = new SingleLL();
// Recursively clone the next nodes
// Get the first node of clone linked list
// Find last node
while (auxiliary != null && auxiliary.next != null)
{
auxiliary = auxiliary.next;
}
// Set tail node
colon.tail = auxiliary;
return colon;
}
public static void main(String[] args)
{
SingleLL actual = new SingleLL();
//  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
System.out.print("\n Before colon ");
actual.display();
System.out.print("\n After colon ");
colon.display();
System.out.print("\n After add new element ");
colon.display();
System.out.print("\n Actual Linked List : ");
actual.display();
}
}``````

#### input

`````` Before colon
Actual Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL

After colon
Colon Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL

Colon Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 10 → NULL

Actual Linked List :  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL``````
``````<?php
/*
Php Program for
*/
{
public \$data;
public \$next;
public	function __construct(\$data)
{
\$this->data = \$data;
\$this->next = NULL;
}
}
class SingleLL
{
public \$tail;
public	function __construct()
{
\$this->tail = NULL;
}
{
{
}
else
{
// Append the node at last position
\$this->tail->next = \$node;
}
\$this->tail = \$node;
}
public	function display()
{
{
"\n");
return;
}
while (\$temp != NULL)
{
echo(" ".\$temp->data.
" →");
// Visit to next node
\$temp = \$temp->next;
}
echo(" NULL".
"\n");
}
// This is cloning the linked list node using recursive
public	function clones(\$node)
{
if (\$node == NULL)
{
return NULL;
}
// Create new node
// Connect with next node
\$auxiliary->next = \$this->clones(\$node->next);
// Return new node
return \$auxiliary;
}
{
\$colon = new SingleLL();
// Recursively clone the next nodes
// Get the first node of clone linked list
// Find last node
while (\$auxiliary != NULL && \$auxiliary->next != NULL)
{
\$auxiliary = \$auxiliary->next;
}
// Set tail node
\$colon->tail = \$auxiliary;
return \$colon;
}
}

function main()
{
\$actual = new SingleLL();
//  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
echo("\n Before colon ");
\$actual->display();
echo("\n After colon ");
\$colon->display();
echo("\n After add new element ");
\$colon->display();
echo("\n Actual Linked List : ");
\$actual->display();
}
main();``````

#### input

`````` Before colon
Actual Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL

After colon
Colon Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL

Colon Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 10 → NULL

Actual Linked List :  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL``````
``````/*
Node JS Program for
*/
{
constructor(data)
{
this.data = data;
this.next = null;
}
}
class SingleLL
{
constructor()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
display()
{
{
return;
}
while (temp != null)
{
process.stdout.write(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
console.log(" NULL");
}
// This is cloning the linked list node using recursive
clones(node)
{
if (node == null)
{
return null;
}
// Create new node
// Connect with next node
auxiliary.next = this.clones(node.next);
// Return new node
return auxiliary;
}
{
var colon = new SingleLL();
// Recursively clone the next nodes
// Get the first node of clone linked list
// Find last node
while (auxiliary != null && auxiliary.next != null)
{
auxiliary = auxiliary.next;
}
// Set tail node
colon.tail = auxiliary;
return colon;
}
}

function main()
{
var actual = new SingleLL();
//  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
process.stdout.write("\n Before colon ");
actual.display();
process.stdout.write("\n After colon ");
colon.display();
process.stdout.write("\n After add new element ");
colon.display();
process.stdout.write("\n Actual Linked List : ");
actual.display();
}
main();``````

#### input

`````` Before colon
Actual Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL

After colon
Colon Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL

Colon Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 10 → NULL

Actual Linked List :  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL``````
``````#  Python 3 Program for
#  Copy linked list using recursion

def __init__(self, data) :
self.data = data
self.next = None

class SingleLL :
def __init__(self) :
self.tail = None

else :
#  Append the node at last position
self.tail.next = node

self.tail = node

def display(self) :
return

while (temp != None) :
print("", temp.data ,"→", end = "")
#  Visit to next node
temp = temp.next

print(" NULL")

#  This is cloning the linked list node using recursive
def clones(self, node) :
if (node == None) :
return None

#  Create new node
#  Connect with next node
auxiliary.next = self.clones(node.next)
#  Return new node
return auxiliary

colon = SingleLL()
#  Recursively clone the next nodes
#  Get the first node of clone linked list
#  Find last node
while (auxiliary != None and auxiliary.next != None) :
auxiliary = auxiliary.next

#  Set tail node
colon.tail = auxiliary
return colon

def main() :
actual = SingleLL()
#   1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
print("\n Before colon ", end = "")
print("\n Actual Linked List :", end = "")
actual.display()
print("\n After colon ", end = "")
print("\n Colon Linked List :", end = "")
colon.display()
print("\n After add new element ", end = "")
print("\n Colon Linked List :", end = "")
colon.display()
print("\n Actual Linked List : ", end = "")
actual.display()

if __name__ == "__main__": main()``````

#### input

`````` Before colon
Actual Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL

After colon
Colon Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL

Colon Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 10 → NULL

Actual Linked List :  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL``````
``````#  Ruby Program for
#  Copy linked list using recursion

attr_accessor :data, :next
def initialize(data)
self.data = data
self.next = nil
end

end

class SingleLL
# Define the accessor and reader of class SingleLL
def initialize()
self.tail = nil
end

else
#  Append the node at last position
self.tail.next = node
end

self.tail = node
end

def display()
return
end

while (temp != nil)
print(" ", temp.data ," →")
#  Visit to next node
temp = temp.next
end

print(" NULL", "\n")
end

#  This is cloning the linked list node using recursive
def clones(node)
if (node == nil)
return nil
end

#  Create new node
#  Connect with next node
auxiliary.next = self.clones(node.next)
#  Return new node
return auxiliary
end

colon = SingleLL.new()
#  Recursively clone the next nodes
#  Get the first node of clone linked list
#  Find last node
while (auxiliary != nil && auxiliary.next != nil)
auxiliary = auxiliary.next
end

#  Set tail node
colon.tail = auxiliary
return colon
end

end

def main()
actual = SingleLL.new()
#   1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
print("\n Before colon ")
actual.display()
print("\n After colon ")
colon.display()
print("\n After add new element ")
colon.display()
print("\n Actual Linked List : ")
actual.display()
end

main()``````

#### input

`````` Before colon
Actual Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL

After colon
Colon Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL

Colon Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 10 → NULL

Actual Linked List :  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
``````
``````/*
Scala Program for
*/
{
def this(data: Int)
{
this(data,null);
}
}
{
def this()
{
this(null,null);
}
def addNode(data: Int): Unit = {
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
def display(): Unit = {
{
return;
}
while (temp != null)
{
print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
println(" NULL");
}
// This is cloning the linked list node using recursive
if (node == null)
{
return null;
}
// Create new node
// Connect with next node
auxiliary.next = clones(node.next);
// Return new node
return auxiliary;
}
var colon: SingleLL = new SingleLL();
// Recursively clone the next nodes
// Get the first node of clone linked list
// Find last node
while (auxiliary != null && auxiliary.next != null)
{
auxiliary = auxiliary.next;
}
// Set tail node
colon.tail = auxiliary;
return colon;
}
}
object Main
{
def main(args: Array[String]): Unit = {
var actual: SingleLL = new SingleLL();
//  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
print("\n Before colon ");
actual.display();
print("\n After colon ");
colon.display();
print("\n After add new element ");
colon.display();
print("\n Actual Linked List : ");
actual.display();
}
}``````

#### input

`````` Before colon
Actual Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL

After colon
Colon Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL

Colon Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 10 → NULL

Actual Linked List :  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL``````
``````/*
Swift 4 Program for
*/
{
var data: Int;
init(_ data: Int)
{
self.data = data;
self.next = nil;
}
}
class SingleLL
{
init()
{
self.tail = nil;
}
{
{
}
else
{
// Append the node at last position
self.tail!.next = node;
}
self.tail = node;
}
func display()
{
{
return;
}
while (temp  != nil)
{
print("", temp!.data ,"→", terminator: "");
// Visit to next node
temp = temp!.next;
}
print(" NULL");
}
// This is cloning the linked list node using recursive
{
if (node == nil)
{
return nil;
}
// Create new node
// Connect with next node
auxiliary!.next = self.clones(node!.next);
// Return new node
return auxiliary;
}
{
let colon: SingleLL = SingleLL();
// Recursively clone the next nodes
// Get the first node of clone linked list
// Find last node
while (auxiliary  != nil && auxiliary!.next  != nil)
{
auxiliary = auxiliary!.next;
}
// Set tail node
colon.tail = auxiliary;
return colon;
}
}
func main()
{
let actual: SingleLL = SingleLL();
//  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
print("\n Before colon ", terminator: "");
print("\n Actual Linked List :", terminator: "");
actual.display();
print("\n After colon ", terminator: "");
print("\n Colon Linked List :", terminator: "");
colon.display();
print("\n After add new element ", terminator: "");
print("\n Colon Linked List :", terminator: "");
colon.display();
print("\n Actual Linked List : ", terminator: "");
actual.display();
}
main();``````

#### input

`````` Before colon
Actual Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL

After colon
Colon Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL

Colon Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 10 → NULL

Actual Linked List :  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL``````
``````/*
Kotlin Program for
*/
{
var data: Int;
constructor(data: Int)
{
this.data = data;
this.next = null;
}
}
class SingleLL
{
constructor()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail?.next = node;
}
this.tail = node;
}
fun display(): Unit
{
{
return;
}
while (temp != null)
{
print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
println(" NULL");
}
// This is cloning the linked list node using recursive
{
if (node == null)
{
return null;
}
// Create new node
// Connect with next node
auxiliary.next = this.clones(node.next);
// Return new node
return auxiliary;
}
{
val colon: SingleLL = SingleLL();
// Recursively clone the next nodes
// Get the first node of clone linked list
// Find last node
while (auxiliary != null && auxiliary.next != null)
{
auxiliary = auxiliary.next;
}
// Set tail node
colon.tail = auxiliary;
return colon;
}
}
fun main(args: Array < String > ): Unit
{
val actual: SingleLL = SingleLL();
//  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
print("\n Before colon ");
actual.display();
print("\n After colon ");
colon.display();
print("\n After add new element ");
colon.display();
print("\n Actual Linked List : ");
actual.display();
}``````

#### input

`````` Before colon
Actual Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL

After colon
Colon Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL

Colon Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 10 → NULL

Actual Linked List :  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL``````

## Output Explanation

The code copies the original linked list recursively and displays both the original and the copied linked lists. It also demonstrates adding a new element to the copied linked list without affecting the original linked list.

## Time Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes in the linked list. This is because each node is visited exactly once during the traversal.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post