题目：翻转单词顺序。

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student."，则输出"student. a am I"。

解法

第一步先翻转句子中所有的字符，比如翻转"I am a student."中所有的字符得到".tneduts a ma I"，此时不但翻转了句子中单词的顺序，连单词内的字符顺序也被翻转了。第二步再翻转每个单词中字符的顺序，就得到了"student. am I"。

void Reverse(char *pBegin, char *pEnd)
{
      if(pBegin == nullptr || pEnd == nullptr)
          return;
      while(pBegin < pEnd)
      {
              char temp = *pBegin;
              *pBegin = *pEnd;
              *pEnd = temp;
              
              pBegin ++, pEnd --;
      }
}

char* ReverseSentence(char *pData)
{
    if(pData == nullptr)
          return nullptr;
    char *pBegin = pData;
    char *pEnd = pData;
    while(*pEnd != '\0')
            pEnd ++;
     pEnd--;

    //翻转整个句子
    Reverse(pBegin,pEnd);
    
    //翻转句子中的每个单词
    pBegin = pEnd = pData;
    while(*pBegin != '\0')
    {
          if(*pBegin == '')
          {
              pBegin ++;
              pEnd ++;
          }
          else if(*pEnd == '' || *pEnd == '\0')
          {
              Reverse(pBegin,--pEnd);
              pBegin = ++pEnd;
          }
          else
          {
              pEnd ++;
          }
    }
    return pData;
}

在英语句子中，单词背空格符号分割，因此我们可以通过扫描空格来确定每个单词的起始位置和终止位置。在上述代码的翻转每个单词阶段，指针 pBegin 指向单词的第一个字符，而指针 pEnd 指向单词的最后一个字符。

Swift实现

fileprivate func _reverse<T>(_ chars: inout [T], _ start: Int, _ end: Int) {
  var start = start, end = end
  while start < end {
      _swap(&chars, start, end)
      start += 1
      end -= 1
  }
}

func reverseWords(s: String?) -> String? {
    guard let s = s else {
         return nil
    }
    var chars = Array(s.characters), start = 0
    _reverse(&chars, 0, chars.count - 1)
    for i in 0 ..< chars.count {
        if i == chars.count - 1 || chars[i + 1] == " " {
            _reverse(&chars, start, i)
            start = i + 2
        }
    }
    return String(chars)
}

时间复杂度为O(n)。