Deep copy a linked list with random pointer

Question:Given a linked list which has a next pointer pointing to the next element in the list and a random pointer pointing to the random element in the list. Implement a method to deep copy this linked list such that the random pointer still copies to the same node in the new list.
1. Create a copy of each node and insert the element next to the original node, iterate through the list.
2. Now the new list has 2N elements (assuming original one has N elements). Then assign the random pointer’s next node to the copied node’s random pointer. Iterate through the list.
3. Now break the list in two lists, original and new.

This logic is implemented in the method DeepCopy in the page.

Find the existence of a loop in a linked list

Question: Find if given linked list has a loop or not. If a list has a loop, then you will never stop traversing the list and visit the same set of elements again and again. For example,
1->2->3->4->5 in the list, 5 should point to NULL. However if 5 points to 3 then it has a loop 3->4->5->3->4->5->3….

Answer: Take two pointers temp1 and temp2. Advance temp1 by one element at a time and temp2 by two elements at a time and keep doing this until temp1 / temp2 is null or temp1 and temp2 pointing to the same element. If it is later case then there is a loop, otherwise there is no loop/

The code for this is defined in the method DetectLoop in the page.

Find the Kth element from the end in a linked list

Question: Given a linked list, find the kth element from the end of the list.
Answer: Take two pointers temp1 and temp2, assign both of them to head. Move one pointer (say temp1) K times so that the distance between temp1 and temp2 is k.
Now start moving both the pointers until temp1 reach the end of the list. Now temp2 points to the kth element from the end of the list.

For source code see GetKthElementFromEnd method in the page.