Next Permutation

The logic is not very hard. However it is easy to make mistake at several places.

General example: 1 3 5 4 2
Step1: scan from right to left, locate the first decreasing number. 1 3 5 4 2
Step2: swap it with the smallest-larger-number (1 3 5 4 2) on the right.  1 4 5 3 2
Step3: reverse all the numbers on the right. 1 4 2 3 5


Need to pay attention to two test cases:
1) repeated value: 5 1 1   
2) reverse order: 5 4 3 2 1

Leetcode Insertion Sort List

For insertion sort, the insertion is usually performed in a backward fashion:
start from the node just ahead, move left one by one, until find the correct insertion point (first left-node which is smaller than the insertee).

However, for single linked list, moving backwards is very hard since pointers to node's previous node is not available.  So each time we have to seek for insert-position from the list-head.

Then what? After find the insert-position, what should we do next?

Take the example of   0  3  4  5  1,  where 1 is the node to be inserted.
It is easy to identify that we need to insert in front of 3. In order to do this in place, I break this action into the following steps:

1. move the sub-sequence 3  4  5  to the right by one:  0  _  3  4  5 
2. insert 1 to the places which held 3 before: 0  1  3  4  5 

Talking about the implementation of the above, the choice can either be: just modify the values of related ListNode , or break the link and insert the nodes into the correct position.

I implemented via modifying values.

Linked List Cycle II

Notation:

1. From head to cycleStartPoint:  a
2. From cycleStartPoint to encounter point: b
3. Number of nodes in in cycle: r
4. Total length of the list: L

First step: start fast runner and slow runner, stop when then encounter each other.

• slower runner move:  s = a + b; (eq1)
• fast runner move: S = 2s = s + kr; (eq2)

      From eq1 and eq2, we can get: s = kr = a + b;

• From kr = a + b
• (k-1)r + r = a + b
• (k-1)r + (L - a) = a + b
• (k-1)r + (L - a - b) = a

So: a = (k-1) cycles + (distance between encounter-point and cycle-start-point)

Step2: Move fast runner to head. Start both fast-runner and slow-runner, both move one node each step.

They will encounter each other again at cycle-start-point.