输入一个链表的头节点，从尾到头反过来打印出每个节点的值。链表节点定义如下：

1
2
3
4
5

struct ListNode 
{
    int m_mKey;
    ListNode *m_pNext;
}

• 内存分配不是在创建链表时一次性完成的，由于没有闲置的内存，链表的空间效率比数组高。
• 如果我们打算修改输入的数据，最好先问面试官是不是允许修改。
• 典型的后进先出，可以用栈实现这种顺序。递归本质上就是一个栈结构，但有可能导致函数调用栈溢出，显然用栈基于循环实现的代码的鲁棒性要好一些。
• 考查对循环、递归、栈 3 个相互关联的概念的理解。

Source Code

请实现一个函数，把字符串中的每个空格替换成“20%”。例如，输入“We are happy.”，则输出“We%20are%20happy.”。

• URL参数中含有特殊字符，如空格、”#”等。会导致服务器端无法获得正确的参数值，转换规则：”%”后面跟上 ASCII 码的两位十六进制的表示。
• 从前往后复制每个字符则需要重复移动数字多次（O(n^2)），从后往前复制，这样就能减少移动的次数，从而提高效率（O(n)）。能清晰地分析出两种不同方法的时间效率各是多少。
• 画一两个示意图解释自己的思路（两个指针），既能帮助我们厘清思路，也能使我们和面试官的交流变得更加高效。
  Read more »

在一个长度为 n+1 的数组里的所有数字都在 1～n 的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为 8 的数组 [2, 3, 5, 4, 3, 2, 6, 7]，那么对应的输出是重复的数字 2 或者 3。

• 可以创建一个长度为 n+1 的辅助数组，该方案需要 O(n) 的辅助空间。
• 某范围里数字的个数对解决这个问题很重要。
• 函数 countRange 将被调用 O(logn) 次，每次需要 O(n) 的时间，总时间复杂度是 O(nlogn)，相当于以时间换空间。
• 交流的重要性：面试官提出不同的功能要求或者性能要求，我们最终选取的算法也将不同。
• 能快速、正确地实现二分查找算法的代码。

Source Code

在一个长度为 n 的数组里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为 7 的数组 [2, 3, 1, 0, 2, 5, 3]，那么对应的输出是重复的数字 2 或者 3。

• 排序一个长度为 n 的数组需要 O(nlogn) 的时间。
• 利用哈希表可以实现时间复杂度为 O(n) 的算法，但代价是一个空间复杂度为 O(n) 的哈希表。
• 重复数字通过指针，传递给函数的调用者。
• 尽管有一个两重循环，但每个数字最多只要交换两次就能找到属于它自己的位置，故时间复杂度是 O(n)。
• 一维数组在内存中占据连续的空间，可以根据下标定位对应的元素。
• 问题比较复杂时，关键是能否通过具体的例子找出其中的规律。

Source Code

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

• 通过分析简单具体的例子，试图寻找普遍的规律。
• 在二维数组的中间选取一个数字，转变成从数组的一个角上选取数字。
• 如果该数字大于要查找的数字，则剔除这个数字所在列；如果该数字小于要查找的数字，则剔除这个数字所在的行。
• 也可以选取左下角的数字。
• 注意特殊输入测试（空指针）。
• 根据行号和列号计算出相对于数组首地址的偏移量。

Source Code