Given a special list, whose node have extra pointer random which point to some other node in linked list. Create another list that is copy of the given list. Also, make sure that random pointer is also allocated to respective node in new list.

Traverse the list and go on adding nodes to the list, which have same value but have random pointer points to null. Now traverse the modified list again. Let us call the node, which was already present in the list as old node and the node, which is added as new node. Find the random pointer node pointed of old node and assign its next node to the random pointer of new node. Follow this procedure for all the nodes. Finally separate the old and new nodes. The list formed by new nodes is the desired list.

Transcribed Image Text:

//Sorts a given list by selection sort //Input: An array A[ 0..n-1] of orderable elements. //Output: List A[0..n-1] sorted in ascending order Algorithm SelectionSort (A[ 0..n-1]) for i to n - 2 do min = i for j =i + 1 to n - 1 do if A[j] A[min] min = j swap A[i] and A[min]