回文判断

    那么，我们的第一个问题就是：判断一个字串是否是回文？

    回文判断是一类典型的问题，尤其是与字符串结合后呈现出多姿多彩，在实际中使用也比较广泛，而且也是面试题中的常客，所以本节就结合几个典型的例子来体味下回文之趣。

    同时从字符串头尾开始向中间扫描字串，如果所有字符都一样，那么这个字串就是一个回文。采用这种方法的话，我们只需要维护头部和尾部两个扫描指针即可。

    这是一个直白且效率不错的实现，时间复杂度：O(n)，空间复杂度：O(1)。

    解法二

    上述解法一从两头向中间扫描，那么是否还有其它办法呢？我们可以先从中间开始、然后向两边扩展查看字符是否相等。参考代码如下：

    2. {
    3.      if (s == NULL || n < 1)
    4.      {
    5.      }
    6.      const char* first, *second;
    9.      int m = ((n >> 1) - 1) >= 0 ? (n >> 1) - 1 : 0;
    10.      first = s + m;
    11.      second = s + n - 1 - m;
    13.      while (first >= s)
    14.          if (*first!= *second)
    16.              return false;
    17.          }
    18.          --first;
    19.          ++second;
    20.      }
    21.      return true;
    22. }

    时间复杂度：O(n)，空间复杂度：O(1)。

    1、判断一条单向链表是不是“回文”

    分析：对于单链表结构，可以用两个指针从两端或者中间遍历并判断对应字符是否相等。但这里的关键就是如何朝两个方向遍历。由于单链表是单向的，所以要向两个方向遍历的话，可以采取经典的快慢指针的方法，即先位到链表的中间位置，再将链表的后半逆置，最后用两个指针同时从链表头部和中间开始同时遍历并比较即可。

    2、判断一个栈是不是“回文”