Link List common Problem

1) How to find a loop in link list ?

This link http://www.programmerinterview.com/index.php/data-structures/how-to-find-if-a-linked-list-is-circular-or-has-a-cycle-or-it-ends/ does a good job of explaining  loop finding in link list.

Recursive Puzzle

Given a string such as: 123456abcdef consisting of n/2 integers followed by n/2 characters. Reorder the string to contain as 1a2b3c4d5e6f . The algorithm should be in-place.

Sol :

1) Divide the string into two partitions, number part and letter part

2) Divide each of those partitions into two more (equal sized)

3) Swap the second the third partition (inner number and inner letter)

4) Recurse on the original two partitions (with their newly swapped bits)

5) Stop when the partition has a size of 2 

For example:

123456abcdef -> 123456 abcdef -> 123 456 abc def -> 123 abc 456 def

123abc -> 123 abc -> 12 3 ab c -> 12 ab 3 c

12 ab -> 1 2 a b -> 1 a 2 b

... etc

And the same for the other half of the recursion..

All can be done in place with the only gotcha being swapping partitions that aren't the same size which will be off by one, so not difficult to handle.

source: http://stackoverflow.com/questions/7222102/reorder-a-string-by-half-the-character