题目地址：

https://www.lintcode.com/problem/reverse-only-letters/description

给定一个字符串$s$，翻转之，但要保持非字母的字符原地不动。返回翻转后的字符串。

思路是对撞双指针。左指针先右移到字母，然后右指针左移到字母，进行调换，接着继续向中间走，直到两个指针相撞，则退出循环。代码如下：

public class Solution { /** * @param S: Customary string * @return: Reversed string */ public String ReverseOnlyLetters(String S) { // write your code here char[] s = S.toCharArray(); for (int i = 0, j = s.length - 1; i < j; ) { while (i < j && !Character.isLetter(s[i])) { i++; } while (i < j && !Character.isLetter(s[j])) { j--; } swap(s, i, j); i++; j--; } return new String(s); } private void swap(char[] s, int i, int j) { char tmp = s[i]; s[i] = s[j]; s[j] = tmp; } }

时空复杂度$O(n)$。