Skip to main content

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
struct LinkNode *clones(struct LinkNode *node)
{
    if (node == NULL)
    {
        return NULL;
    }
    // Create new node
    struct LinkNode *auxiliary = createNode(node->data);
    // Connect with next node
    auxiliary->next = clones(node->next);
    // Return new node
    return auxiliary;
}

// Function to clone the entire linked list recursively
struct SingleLL *cloneLinkList(struct SingleLL *actual)
{
    // Create new linked list
    struct SingleLL *colon = newLinkedList();
    // Recursively clone the next nodes
    colon->head = clones(actual->head);
    // Find the last node
    struct LinkNode *auxiliary = colon->head;
    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>

// Linked List LinkNode
struct LinkNode
{
	int data;
	struct LinkNode *next;
};
// Singly linked list 
struct SingleLL
{
	struct LinkNode *head;
	struct LinkNode *tail;
};
// Returns the new linked list
struct SingleLL *newLinkedList()
{
	// 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->head = NULL;
		sll->tail = NULL;
	}
	return sll;
}
// Returns the new node of linked list
struct LinkNode *createNode(int data)
{
	// Create dynamic node
	struct LinkNode *node = (struct LinkNode *) malloc(sizeof(struct LinkNode));
	if (node == NULL)
	{
		printf("Memory overflow to Create LinkNode\n");
	}
	else
	{
		// Set initial node value
		node->data = data;
		node->next = NULL;
	}
	return node;
}
// Handles the request of adding new node in linked list
void addNode(struct SingleLL *sll, int data)
{
	struct LinkNode *node = createNode(data);
	if (sll->head == NULL)
	{
		sll->head = node;
	}
	else
	{
		// Append the node at last position
		sll->tail->next = node;
	}
	sll->tail = node;
}
// Display linked list element
void display(struct SingleLL *sll)
{
	if (sll->head == NULL)
	{
		return;
	}
	struct LinkNode *temp = sll->head;
	// iterating linked list elements
	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
struct LinkNode *clones(struct LinkNode *node)
{
	if (node == NULL)
	{
		return NULL;
	}
	// Create new node
	struct LinkNode *auxiliary = createNode(node->data);
	// Connect with next node
	auxiliary->next = clones(node->next);
	// Return new node
	return auxiliary;
}
struct SingleLL *cloneLinkList(struct SingleLL *actual)
{
	// Create new linked list
	struct SingleLL *colon = newLinkedList();
	// Recursively clone the next nodes
	colon->head = clones(actual->head);
	// Get the first node of clone linked list
	struct LinkNode *auxiliary = colon->head;
	// 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[])
{
	struct SingleLL *actual = newLinkedList();
	//  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
	addNode(actual, 1);
	addNode(actual, 2);
	addNode(actual, 3);
	addNode(actual, 4);
	addNode(actual, 5);
	addNode(actual, 6);
	addNode(actual, 7);
	addNode(actual, 8);
	// Display given linked list
	printf("\n Before colon  ");
	printf("\n Actual Linked List  : ");
	display(actual);
	struct SingleLL *colon = cloneLinkList(actual);
	// Display resultant linked list
	printf("\n After colon  ");
	printf("\n Colon Linked List  : ");
	display(colon);
	// Display resultant linked list
	printf("\n After add new element   ");
	printf("\n Colon Linked List  : ");
	addNode(colon, 10);
	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

 After add new element
 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 
  Copy linked list using recursion
*/
// Linked list node
class LinkNode
{
	public int data;
	public LinkNode next;
	public LinkNode(int data)
	{
		this.data = data;
		this.next = null;
	}
}
public class SingleLL
{
	public LinkNode head;
	public LinkNode tail;
	public SingleLL()
	{
		this.head = null;
		this.tail = null;
	}
	// Add new Node at end of linked list 
	public void addNode(int data)
	{
		LinkNode node = new LinkNode(data);
		if (this.head == null)
		{
			this.head = node;
		}
		else
		{
			// Append the node at last position
			this.tail.next = node;
		}
		this.tail = node;
	}
	// Display linked list element
	public void display()
	{
		if (this.head == null)
		{
			System.out.println("\n Empty linked list");
			return;
		}
		LinkNode temp = this.head;
		//iterating linked list elements
		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
	public LinkNode clones(LinkNode node)
	{
		if (node == null)
		{
			return null;
		}
		// Create new node
		LinkNode auxiliary = new LinkNode(node.data);
		// Connect with next node
		auxiliary.next = clones(node.next);
		// Return new node
		return auxiliary;
	}
	public SingleLL cloneLinkList()
	{
		// Create new linked list
		SingleLL colon = new SingleLL();
		// Recursively clone the next nodes
		colon.head = clones(this.head);
		// Get the first node of clone linked list
		LinkNode auxiliary = colon.head;
		// 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();
      	// Creating linked list
		//  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
		actual.addNode(1);
		actual.addNode(2);
		actual.addNode(3);
		actual.addNode(4);
		actual.addNode(5);
		actual.addNode(6);
		actual.addNode(7);
		actual.addNode(8);
		// Display given linked list
		System.out.print("\n Before colon ");
		System.out.print("\n Actual Linked List :");
		actual.display();
		// Colon linked list
		SingleLL colon = actual.cloneLinkList();
		// Display resultant linked list
		System.out.print("\n After colon ");
		System.out.print("\n Colon Linked List :");
		colon.display();
		// Display resultant linked list
		System.out.print("\n After add new element ");
		System.out.print("\n Colon Linked List :");
		colon.addNode(10);
		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

 After add new element
 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 
  Copy linked list using recursion
*/

// Linked list node
class LinkNode
{
	public: 
    int data;
	LinkNode *next;
	LinkNode(int data)
	{
		this->data = data;
		this->next = NULL;
	}
};
class SingleLL
{
	public: 
    LinkNode *head;
	LinkNode *tail;
	SingleLL()
	{
		this->head = NULL;
		this->tail = NULL;
	}
	// Add new Node at end of linked list 
	void addNode(int data)
	{
		LinkNode *node = new LinkNode(data);
		if (this->head == NULL)
		{
			this->head = node;
		}
		else
		{
			// Append the node at last position
			this->tail->next = node;
		}
		this->tail = node;
	}
	// Display linked list element
	void display()
	{
		if (this->head == NULL)
		{
			cout << "\n Empty linked list" << endl;
			return;
		}
		LinkNode *temp = this->head;
		//iterating linked list elements
		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
	LinkNode *clones(LinkNode *node)
	{
		if (node == NULL)
		{
			return NULL;
		}
		// Create new node
		LinkNode *auxiliary = new LinkNode(node->data);
		// Connect with next node
		auxiliary->next = this->clones(node->next);
		// Return new node
		return auxiliary;
	}
	SingleLL *cloneLinkList()
	{
		// Create new linked list
		SingleLL *colon = new SingleLL();
		// Recursively clone the next nodes
		colon->head = this->clones(this->head);
		// Get the first node of clone linked list
		LinkNode *auxiliary = colon->head;
		// 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();
	// Creating linked list
	//  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
	actual->addNode(1);
	actual->addNode(2);
	actual->addNode(3);
	actual->addNode(4);
	actual->addNode(5);
	actual->addNode(6);
	actual->addNode(7);
	actual->addNode(8);
	// Display given linked list
	cout << "\n Before colon ";
	cout << "\n Actual Linked List :";
	actual->display();
	// Colon linked list
	SingleLL *colon = actual->cloneLinkList();
	// Display resultant linked list
	cout << "\n After colon ";
	cout << "\n Colon Linked List :";
	colon->display();
	// Display resultant linked list
	cout << "\n After add new element ";
	cout << "\n Colon Linked List :";
	colon->addNode(10);
	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

 After add new element
 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 
  Copy linked list using recursion
*/
// Linked list node
class LinkNode
{
	public int data;
	public LinkNode next;
	public LinkNode(int data)
	{
		this.data = data;
		this.next = null;
	}
}
public class SingleLL
{
	public LinkNode head;
	public LinkNode tail;
	public SingleLL()
	{
		this.head = null;
		this.tail = null;
	}
	// Add new Node at end of linked list 
	public void addNode(int data)
	{
		LinkNode node = new LinkNode(data);
		if (this.head == null)
		{
			this.head = node;
		}
		else
		{
			// Append the node at last position
			this.tail.next = node;
		}
		this.tail = node;
	}
	// Display linked list element
	public void display()
	{
		if (this.head == null)
		{
			System.out.println("\n Empty linked list");
			return;
		}
		LinkNode temp = this.head;
		//iterating linked list elements
		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
	public LinkNode clones(LinkNode node)
	{
		if (node == null)
		{
			return null;
		}
		// Create new node
		LinkNode auxiliary = new LinkNode(node.data);
		// Connect with next node
		auxiliary.next = clones(node.next);
		// Return new node
		return auxiliary;
	}
	public SingleLL cloneLinkList()
	{
		// Create new linked list
		SingleLL colon = new SingleLL();
		// Recursively clone the next nodes
		colon.head = clones(this.head);
		// Get the first node of clone linked list
		LinkNode auxiliary = colon.head;
		// 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();
		// Creating linked list
		//  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
		actual.addNode(1);
		actual.addNode(2);
		actual.addNode(3);
		actual.addNode(4);
		actual.addNode(5);
		actual.addNode(6);
		actual.addNode(7);
		actual.addNode(8);
		// Display given linked list
		System.out.print("\n Before colon ");
		System.out.print("\n Actual Linked List :");
		actual.display();
		// Colon linked list
		SingleLL colon = actual.cloneLinkList();
		// Display resultant linked list
		System.out.print("\n After colon ");
		System.out.print("\n Colon Linked List :");
		colon.display();
		// Display resultant linked list
		System.out.print("\n After add new element ");
		System.out.print("\n Colon Linked List :");
		colon.addNode(10);
		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

 After add new element
 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 
  Copy linked list using recursion
*/
// Linked list node
class LinkNode
{
	public $data;
	public $next;
	public	function __construct($data)
	{
		$this->data = $data;
		$this->next = NULL;
	}
}
class SingleLL
{
	public $head;
	public $tail;
	public	function __construct()
	{
		$this->head = NULL;
		$this->tail = NULL;
	}
	// Add new Node at end of linked list 
	public	function addNode($data)
	{
		$node = new LinkNode($data);
		if ($this->head == NULL)
		{
			$this->head = $node;
		}
		else
		{
			// Append the node at last position
			$this->tail->next = $node;
		}
		$this->tail = $node;
	}
	// Display linked list element
	public	function display()
	{
		if ($this->head == NULL)
		{
			echo("\n Empty linked list".
				"\n");
			return;
		}
		$temp = $this->head;
		//iterating linked list elements
		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
		$auxiliary = new LinkNode($node->data);
		// Connect with next node
		$auxiliary->next = $this->clones($node->next);
		// Return new node
		return $auxiliary;
	}
	public	function cloneLinkList()
	{
		// Create new linked list
		$colon = new SingleLL();
		// Recursively clone the next nodes
		$colon->head = $this->clones($this->head);
		// Get the first node of clone linked list
		$auxiliary = $colon->head;
		// 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();
	// Creating linked list
	//  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
	$actual->addNode(1);
	$actual->addNode(2);
	$actual->addNode(3);
	$actual->addNode(4);
	$actual->addNode(5);
	$actual->addNode(6);
	$actual->addNode(7);
	$actual->addNode(8);
	// Display given linked list
	echo("\n Before colon ");
	echo("\n Actual Linked List :");
	$actual->display();
	// Colon linked list
	$colon = $actual->cloneLinkList();
	// Display resultant linked list
	echo("\n After colon ");
	echo("\n Colon Linked List :");
	$colon->display();
	// Display resultant linked list
	echo("\n After add new element ");
	echo("\n Colon Linked List :");
	$colon->addNode(10);
	$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

 After add new element
 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 
  Copy linked list using recursion
*/
// Linked list node
class LinkNode
{
	constructor(data)
	{
		this.data = data;
		this.next = null;
	}
}
class SingleLL
{
	constructor()
	{
		this.head = null;
		this.tail = null;
	}
	// Add new Node at end of linked list 
	addNode(data)
	{
		var node = new LinkNode(data);
		if (this.head == null)
		{
			this.head = node;
		}
		else
		{
			// Append the node at last position
			this.tail.next = node;
		}
		this.tail = node;
	}
	// Display linked list element
	display()
	{
		if (this.head == null)
		{
			console.log("\n Empty linked list");
			return;
		}
		var temp = this.head;
		//iterating linked list elements
		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
		var auxiliary = new LinkNode(node.data);
		// Connect with next node
		auxiliary.next = this.clones(node.next);
		// Return new node
		return auxiliary;
	}
	cloneLinkList()
	{
		// Create new linked list
		var colon = new SingleLL();
		// Recursively clone the next nodes
		colon.head = this.clones(this.head);
		// Get the first node of clone linked list
		var auxiliary = colon.head;
		// 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();
	// Creating linked list
	//  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
	actual.addNode(1);
	actual.addNode(2);
	actual.addNode(3);
	actual.addNode(4);
	actual.addNode(5);
	actual.addNode(6);
	actual.addNode(7);
	actual.addNode(8);
	// Display given linked list
	process.stdout.write("\n Before colon ");
	process.stdout.write("\n Actual Linked List :");
	actual.display();
	// Colon linked list
	var colon = actual.cloneLinkList();
	// Display resultant linked list
	process.stdout.write("\n After colon ");
	process.stdout.write("\n Colon Linked List :");
	colon.display();
	// Display resultant linked list
	process.stdout.write("\n After add new element ");
	process.stdout.write("\n Colon Linked List :");
	colon.addNode(10);
	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

 After add new element
 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

#  Linked list node
class LinkNode :
	def __init__(self, data) :
		self.data = data
		self.next = None
	

class SingleLL :
	def __init__(self) :
		self.head = None
		self.tail = None
	
	#  Add new Node at end of linked list 
	def addNode(self, data) :
		node = LinkNode(data)
		if (self.head == None) :
			self.head = node
		else :
			#  Append the node at last position
			self.tail.next = node
		
		self.tail = node
	
	#  Display linked list element
	def display(self) :
		if (self.head == None) :
			print("\n Empty linked list")
			return
		
		temp = self.head
		# iterating linked list elements
		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
		auxiliary = LinkNode(node.data)
		#  Connect with next node
		auxiliary.next = self.clones(node.next)
		#  Return new node
		return auxiliary
	
	def cloneLinkList(self) :
		#  Create new linked list
		colon = SingleLL()
		#  Recursively clone the next nodes
		colon.head = self.clones(self.head)
		#  Get the first node of clone linked list
		auxiliary = colon.head
		#  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()
	#  Creating linked list
	#   1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
	actual.addNode(1)
	actual.addNode(2)
	actual.addNode(3)
	actual.addNode(4)
	actual.addNode(5)
	actual.addNode(6)
	actual.addNode(7)
	actual.addNode(8)
	#  Display given linked list
	print("\n Before colon ", end = "")
	print("\n Actual Linked List :", end = "")
	actual.display()
	#  Colon linked list
	colon = actual.cloneLinkList()
	#  Display resultant linked list
	print("\n After colon ", end = "")
	print("\n Colon Linked List :", end = "")
	colon.display()
	#  Display resultant linked list
	print("\n After add new element ", end = "")
	print("\n Colon Linked List :", end = "")
	colon.addNode(10)
	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

 After add new element
 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

#  Linked list node
class LinkNode 
	# Define the accessor and reader of class LinkNode
	attr_reader :data, :next
	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
	attr_reader :head, :tail
	attr_accessor :head, :tail
	def initialize() 
		self.head = nil
		self.tail = nil
	end

	#  Add new Node at end of linked list 
	def addNode(data) 
		node = LinkNode.new(data)
		if (self.head == nil) 
			self.head = node
		else 
			#  Append the node at last position
			self.tail.next = node
		end

		self.tail = node
	end

	#  Display linked list element
	def display() 
		if (self.head == nil) 
			print("\n Empty linked list", "\n")
			return
		end

		temp = self.head
		# iterating linked list elements
		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
		auxiliary = LinkNode.new(node.data)
		#  Connect with next node
		auxiliary.next = self.clones(node.next)
		#  Return new node
		return auxiliary
	end

	def cloneLinkList() 
		#  Create new linked list
		colon = SingleLL.new()
		#  Recursively clone the next nodes
		colon.head = self.clones(self.head)
		#  Get the first node of clone linked list
		auxiliary = colon.head
		#  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()
	#  Creating linked list
	#   1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
	actual.addNode(1)
	actual.addNode(2)
	actual.addNode(3)
	actual.addNode(4)
	actual.addNode(5)
	actual.addNode(6)
	actual.addNode(7)
	actual.addNode(8)
	#  Display given linked list
	print("\n Before colon ")
	print("\n Actual Linked List :")
	actual.display()
	#  Colon linked list
	colon = actual.cloneLinkList()
	#  Display resultant linked list
	print("\n After colon ")
	print("\n Colon Linked List :")
	colon.display()
	#  Display resultant linked list
	print("\n After add new element ")
	print("\n Colon Linked List :")
	colon.addNode(10)
	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

 After add new element 
 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 
  Copy linked list using recursion
*/
// Linked list node
class LinkNode(var data: Int , var next: LinkNode)
{
	def this(data: Int)
	{
		this(data,null);
	}
}
class SingleLL(var head: LinkNode , var tail: LinkNode)
{
	def this()
	{
		this(null,null);
	}
	// Add new Node at end of linked list 
	def addNode(data: Int): Unit = {
		var node: LinkNode = new LinkNode(data);
		if (this.head == null)
		{
			this.head = node;
		}
		else
		{
			// Append the node at last position
			this.tail.next = node;
		}
		this.tail = node;
	}
	// Display linked list element
	def display(): Unit = {
		if (this.head == null)
		{
			println("\n Empty linked list");
			return;
		}
		var temp: LinkNode = this.head;
		//iterating linked list elements
		while (temp != null)
		{
			print(" " + temp.data + " →");
			// Visit to next node
			temp = temp.next;
		}
		println(" NULL");
	}
	// This is cloning the linked list node using recursive
	def clones(node: LinkNode): LinkNode = {
		if (node == null)
		{
			return null;
		}
		// Create new node
		var auxiliary: LinkNode = new LinkNode(node.data);
		// Connect with next node
		auxiliary.next = clones(node.next);
		// Return new node
		return auxiliary;
	}
	def cloneLinkList(): SingleLL = {
		// Create new linked list
		var colon: SingleLL = new SingleLL();
		// Recursively clone the next nodes
		colon.head = clones(this.head);
		// Get the first node of clone linked list
		var auxiliary: LinkNode = colon.head;
		// 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();
		// Creating linked list
		//  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
		actual.addNode(1);
		actual.addNode(2);
		actual.addNode(3);
		actual.addNode(4);
		actual.addNode(5);
		actual.addNode(6);
		actual.addNode(7);
		actual.addNode(8);
		// Display given linked list
		print("\n Before colon ");
		print("\n Actual Linked List :");
		actual.display();
		// Colon linked list
		var colon: SingleLL = actual.cloneLinkList();
		// Display resultant linked list
		print("\n After colon ");
		print("\n Colon Linked List :");
		colon.display();
		// Display resultant linked list
		print("\n After add new element ");
		print("\n Colon Linked List :");
		colon.addNode(10);
		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

 After add new element
 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 
  Copy linked list using recursion
*/
// Linked list node
class LinkNode
{
	var data: Int;
	var next: LinkNode? ;
	init(_ data: Int)
	{
		self.data = data;
		self.next = nil;
	}
}
class SingleLL
{
	var head: LinkNode? ;
	var tail: LinkNode? ;
	init()
	{
		self.head = nil;
		self.tail = nil;
	}
	// Add new Node at end of linked list 
	func addNode(_ data: Int)
	{
		let node: LinkNode = LinkNode(data);
		if (self.head == nil)
		{
			self.head = node;
		}
		else
		{
			// Append the node at last position
			self.tail!.next = node;
		}
		self.tail = node;
	}
	// Display linked list element
	func display()
	{
		if (self.head == nil)
		{
			print("\n Empty linked list");
			return;
		}
		var temp: LinkNode? = self.head;
		//iterating linked list elements
		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
	func clones(_ node: LinkNode? )->LinkNode?
	{
		if (node == nil)
		{
			return nil;
		}
		// Create new node
		let auxiliary: LinkNode? = LinkNode(node!.data);
		// Connect with next node
		auxiliary!.next = self.clones(node!.next);
		// Return new node
		return auxiliary;
	}
	func cloneLinkList()->SingleLL
	{
		// Create new linked list
		let colon: SingleLL = SingleLL();
		// Recursively clone the next nodes
		colon.head = self.clones(self.head);
		// Get the first node of clone linked list
		var auxiliary: LinkNode? = colon.head;
		// 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();
	// Creating linked list
	//  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
	actual.addNode(1);
	actual.addNode(2);
	actual.addNode(3);
	actual.addNode(4);
	actual.addNode(5);
	actual.addNode(6);
	actual.addNode(7);
	actual.addNode(8);
	// Display given linked list
	print("\n Before colon ", terminator: "");
	print("\n Actual Linked List :", terminator: "");
	actual.display();
	// Colon linked list
	let colon: SingleLL = actual.cloneLinkList();
	// Display resultant linked list
	print("\n After colon ", terminator: "");
	print("\n Colon Linked List :", terminator: "");
	colon.display();
	// Display resultant linked list
	print("\n After add new element ", terminator: "");
	print("\n Colon Linked List :", terminator: "");
	colon.addNode(10);
	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

 After add new element
 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 
  Copy linked list using recursion
*/
// Linked list node
class LinkNode
{
	var data: Int;
	var next: LinkNode ? ;
	constructor(data: Int)
	{
		this.data = data;
		this.next = null;
	}
}
class SingleLL
{
	var head: LinkNode ? ;
	var tail: LinkNode ? ;
	constructor()
	{
		this.head = null;
		this.tail = null;
	}
	// Add new Node at end of linked list 
	fun addNode(data: Int): Unit
	{
		val node: LinkNode = LinkNode(data);
		if (this.head == null)
		{
			this.head = node;
		}
		else
		{
			// Append the node at last position
			this.tail?.next = node;
		}
		this.tail = node;
	}
	// Display linked list element
	fun display(): Unit
	{
		if (this.head == null)
		{
			println("\n Empty linked list");
			return;
		}
		var temp: LinkNode ? = this.head;
		//iterating linked list elements
		while (temp != null)
		{
			print(" " + temp.data + " →");
			// Visit to next node
			temp = temp.next;
		}
		println(" NULL");
	}
	// This is cloning the linked list node using recursive
	fun clones(node: LinkNode ? ): LinkNode ?
	{
		if (node == null)
		{
			return null;
		}
		// Create new node
		var auxiliary: LinkNode  = LinkNode(node.data);
		// Connect with next node
		auxiliary.next = this.clones(node.next);
		// Return new node
		return auxiliary;
	}
	fun cloneLinkList(): SingleLL
	{
		// Create new linked list
		val colon: SingleLL = SingleLL();
		// Recursively clone the next nodes
		colon.head = this.clones(this.head);
		// Get the first node of clone linked list
		var auxiliary: LinkNode ? = colon.head;
		// 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();
	// Creating linked list
	//  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
	actual.addNode(1);
	actual.addNode(2);
	actual.addNode(3);
	actual.addNode(4);
	actual.addNode(5);
	actual.addNode(6);
	actual.addNode(7);
	actual.addNode(8);
	// Display given linked list
	print("\n Before colon ");
	print("\n Actual Linked List :");
	actual.display();
	// Colon linked list
	val colon: SingleLL = actual.cloneLinkList();
	// Display resultant linked list
	print("\n After colon ");
	print("\n Colon Linked List :");
	colon.display();
	// Display resultant linked list
	print("\n After add new element ");
	print("\n Colon Linked List :");
	colon.addNode(10);
	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

 After add new element
 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.

Last updated on by Kalkicode




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.

New Comment