CareerCup

1. Get length of the loop first :- take two pointers from head, one increment with one second with two, at some point these two pointer will meet(means, that two pointers are in the loop). From that point increment one pointer only and count the size of loop.
2.find the loop point(merging point) : - we know size of loop.Take two pointers at head increment one pointer until the difference between two pointers is equal to size of the loop.then after increment both pointers until they meet(they will meet at merging point).
3.find the kth node from the end of loop:- Two pointers after step-2 will be at merge point. increment one pointer until it goes n, (where n = (size of loop) - k ). that will give kth node form the end of loop

The formatting in the original question got messed up when I posted.

Node 5 should be pointing to Node 3.

This does not exist in case of single link list. suppose 3 is pointing to head and making loop . i.e either 3 points to head or 4 not both, 3 can not point two node at a time.

pretty good!!

Awesome algo Balaji...

1. Get the size of the list, say n.
2. You have a constant value from end, say k.

Start iterating over the list from 0 to n-k+1 th position to get your element.

e.g. We have a list "21 32 43 24 15 12"
1. The size of array would be 5. i.e. n = 6.
2. We want 3rd element from end. i.e. k = 3.
So the desired position is n-k+1 i.e. 6-3+1 = 4th element i.e. 24.

The 'loopNode' will give the nth node.

}}}
public static List loopNode(List head, int n) {
List mergeNode = findMerge(head);
int loopSize = countLoop(mergeNode);

List forwardNode = head;
List backNode;

for (int i = 0; i < loopSize; i++) {
forwardNode = forwardNode.next;
}
for (backNode = head; forwardNode != backNode; forwardNode = forwardNode.next, backNode = backNode.next) {
}
for (int i = 0; i < n; i++) {
backNode = backNode.next;
}
System.out.println(backNode.value);
return backNode;
}
}}}

This function counts the size of the loop.
}}}
public static int countLoop(List node) {
int count = 0;
if(node==null){return 0;};
List start = node.next;
while (start != node) {
count++;
start = start.next;
}
return ++count;
}
}}}

This function is find some node lying inside the loop.

public static List findMerge(List head) {
		List fastNode;
		List slowNode = null;

		if (head == null || head.next == null) {
			return head;
		}
		slowNode = head;
		fastNode = slowNode;

		for (; fastNode != null; fastNode = fastNode.next, slowNode = slowNode.next) {
			fastNode = fastNode.next;
			if(fastNode == null){
				return null;
			}
			if (slowNode == fastNode) {
				return slowNode;
			}
		}
		return null;
	}

What is "end of loop"? How can a loop have an end? Its like a balloon on a thread.

awsome algo

If there is a loop existing, there will be no node after the loop.

first find the beginning of loop: use two pointers, one moves one node each time, another one moves two nodes each time. after they meet, place one of them at head, move them with speed of one together. this time when they meet, you find the beginning of loop.

then use two pointers, one moves 5 steps ahead, they all begin from the beginning of loop. the slower pointer points to the place when the faster one reaches the beginning again.