来源：http://blog.csdn.net/v_july_v/article/details/6322882
题目描述：
定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部，如把字符串abcdef左旋转2位得到字符串cdefab。请实现字符串左旋转的函数。
指针翻转法
咱们先来看个例子，如下：abc defghi，若要让abc移动至最后的过程可以是：abc defghi->def abcghi->def ghiabc
如此，我们可定义俩指针，p1指向ch[0]，p2指向ch[m]；
一下过程循环m次，交换p1和p2所指元素，然后p1++, p2++；。
- 第一步，交换abc 和def ，abc defghi->def abcghi
- 第二步，交换abc 和 ghi，def abcghi->def ghiabc
整个过程，看起来，就是abc 一步一步 向后移动
- abc defghi
- def abcghi
- def ghi abc
//最后的 复杂度是O（m+n）
图解如下：
由上述例子九个元素的序列abcdefghi，您已经看到，m=3时，p2恰好指到了数组最后一个元素，于是，上述思路没有问题。但如果上面例子中i 的后面还有元素列?
即，如果是要左旋十个元素的序列：abcdefghij，ok，下面，就举这个例子，对abcdefghij序列进行左旋转操作：
如果abcdef ghij要变成defghij abc：
abcdef ghij
1. def abc ghij
2. def ghi abc j //接下来，j 步步前移
3. def ghi ab jc
4. def ghi a j bc
5. def ghi j abc
下面，再针对上述过程，画个图清晰说明下，如下所示：
ok，咱们来好好彻底总结一下此思路二：（就4点，请仔细阅读）：
1、首先让p1=ch[0]，p2=ch[m]，即让p1，p2相隔m的距离；
2、判断p2+m-1是否越界，如果没有越界转到3，否则转到4（abcdefgh这8个字母的字符串，以4左旋，那么初始时p2指向e，p2+4越界了，但事实上p2至p2+m-1是m个字符，可以再做一个交换）。
3、不断交换*p1与*p2，然后p1++，p2++，循环m次，然后转到2。
4、此时p2+m-1 已经越界，在此只需处理尾巴。过程如下：
4.1 通过n-p2得到p2与尾部之间元素个数r，即我们要前移的元素个数。
4.2 以下过程执行r次：
ch[p2]<->ch[p2-1]，ch[p2-1]<->ch[p2-2]，....，ch[p1+1]<->ch[p1]；p1++；p2++；
//copyright@July、颜沙 //最终代码，July，updated again，2011.04.17。 #include <iostream> #include <string> using namespace std; void rotate(string &str, int m) { if (str.length() == 0 || m <= 0) return; int n = str.length(); if (m % n <= 0) return; int p1 = 0, p2 = m; int k = (n - m) - n % m; // 交换p1，p2指向的元素，然后移动p1，p2 while (k --) { swap(str[p1], str[p2]); p1++; p2++; } // 重点，都在下述几行。 // 处理尾部，r为尾部左移次数 int r = n - p2; while (r--) { int i = p2; while (i > p1) { swap(str[i], str[i-1]); i--; } p2++; p1++; } //比如一个例子，abcdefghijk // p1 p2 //当执行到这里时，defghi a b c j k //p2+m出界 了， //r=n-p2=2，所以以下过程，要执行循环俩次。 //第一次：j 步步前移，abcjk->abjck->ajbck->jabck //然后，p1++，p2++，p1指a，p2指k。 // p1 p2 //第二次：defghi j a b c k //同理，此后，k步步前移，abck->abkc->akbc->kabc。 } int main() { string ch="abcdefghijk"; rotate(ch,3); cout<<ch<<endl; return 0; }
微信公众号： 猿人谷
如果您认为阅读这篇博客让您有些收获，不妨点击一下右下角的【推荐】
如果您希望与我交流互动，欢迎关注微信公众号
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接。
