Question

Urgent! pls show all ways of how to make a deep copy of each elements in a singly linked list (linear time)

(pls write code with explanation in java! Thanks in advance! )

Answer 1

Showing all ways of how to make a deep copy of each element in a singly linked list in java:

1. Using Hashmap to make a deep copy of the singly linked list by cloning every element of a linked list with next and random pointer:

we need to make a replica of this linked list, that simply means we need to create a deep copy of this LinkedList with difference reference head pointer for both the linked list:

let the singly linked list be:

During the iteration of the first node of the linked list, the hashmap will create a node with the same value. this node will be store as a value of hashmap and the original node reference will be store as a key of hashmap. suppose below is the hashmap:

where n1, n2, n3, and n4 are the copied linked list values copied linked list looks like:

Java code to make a deep copy of the singly linked list by cloning every element of a linked list with next and random pointer:

The output of code is as follow in terms of returning a copied linked list:

so this is how one can get copied LinkedList from the original linked list.

2. One can make a deep copy of a linked list using the override method, that is:

The output of the code is:

3. One can make a copy of the linked list element using the LinkedList clone() method:

The output of the code is as:

so this is some possible way of copy the data of LinkedList to other LinkedList.