两个指针遍历

1，有一个很常见的问题叫子字符串，相关的问题有LCS（最长公共子字符串），还有最长对称子字符串问题。
我们先不讨论算法的优劣，直观的求子字符串方法就是遍历了，我看在求最长对称子字符串时的方法：
简单粗暴的遍历，判断
基于上一篇文章[判断字符串是否对称][1]
[1]: http://www.jianshu.com/p/0eaa1daf93d2
中的issymetrical函数，我们遍历整个字符串对所有的字符串进行检测

#include <iostream>
bool isSymmetrical(char* pbegin, char* pend)
{
    //first check valid
    if (pbegin == NULL || pend == NULL || pbegin>pend)
        return false;

    while (pbegin<pend)
    {
        if (*pbegin == *pend)
        {
            pbegin++;
            pend++;
        }
        else
            return false;
    }
    //if not return yet, return 1
    return true;
}
int getLongestSymmetricalLength(char* pstring)
{
    if (pstring == NULL)
        return 0;
    int symmetricallen = 1;//initialize
    char *pfirst = pstring;
    int len = strlen(pstring);

    //two pointers,the pfirst moves one step and plast moves (n-i)
    while (pfirst < &pstring[len - 1])//pstring[len-1] is the last one
    {
        char* plast = pfirst + 1;
        //并不是指针地址加1，而是地址加上一个偏移量，（等于char的长度）

        while (plast <= &pstring[len - 1])
        {
            if (isSymmetrical(pfirst, plast))// 对pfirst和plast直接的字符串进行判断
            {
                int newlen = plast - pfirst+1;//同样这里相减也得到的是地址差除以偏移量之后的值
                if (newlen > symmetricallen)
                    symmetricallen = newlen;
            }
            plast++;
        }
        pfirst++;
    }
    return symmetricallen;
}

然而这种解法的复杂度为O(n3),遍历字符串复杂度nn，判断又是n.

---

2,第二个问题是，

输出一个单向链表中的倒数第k个元素。

我们可以先遍历一次得到长度然后再遍历n-k个元素

当然有一个更简单的思路：
用两个游标记录位置并遍历。
第一个游标从头开始遍历，然后第二个游标与第一个相差k个元素，当第一个游标结束后，第二个也就是倒数第k个元素。

我们先用一个for循环k次，将第一个指针移动到一个位置；
然后再同时移动两个指针，知道第一个指针到达链表尾。

3，第三个问题：

寻找排序数组中和为定值的两个数。

当然不能遍历所有的组合啊，太低效了。
我们可以这样想，既然是排好序的数组，我们先把第一个和最后一个数加起来看其和与给定值的关系。

• 如果刚好是给定值，输出。
• 如果和小于给定值，那么肯定是最小值太小了，把最小值往上移；
  重复上述；
• 如果和大于给定值，那么肯定是最大值大了，我们把最大值往下移，重复上述。

这里用一个while循环判断两个游标的大小关系就可以啦，，不要想的太复杂！