5.只给定单链表中某个结点p(非空结点)，在p前面插入一个结点。
办法与前者类似，首先分配一个结点q，将q插入在p后，接下来将p中的数据copy入q中，
然后再将要插入的数据记录在p中。

78.链表和数组的区别在哪里？

分析：主要在基本概念上的理解。
但是最好能考虑的全面一点，现在公司招人的竞争可能就在细节上产生，
谁比较仔细，谁获胜的机会就大。

79.
1.编写实现链表排序的一种算法。说明为什么你会选择用这样的方法？
2.编写实现数组排序的一种算法。说明为什么你会选择用这样的方法？
3.请编写能直接实现strstr()函数功能的代码。

80.阿里巴巴一道笔试题

问题描述:
12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种
这个笔试题,很YD,因为把某个递归关系隐藏得很深。

先来几组百度的面试题：

===================

81.第1组百度面试题
1.一个int数组，里面数据无任何限制，要求求出所有这样的数a[i]，
其左边的数都小于等于它，右边的数都大于等于它。
能否只用一个额外数组和少量其它空间实现。
2.一个文件，内含一千万行字符串，每个字符串在1K以内，
要求找出所有相反的串对，如abc和cba。
3.STL的set用什么实现的？为什么不用hash？

82.第2组百度面试题
1.给出两个集合A和B，其中集合A={name}，
集合B={age、sex、scholarship、address、…}，
要求：
问题1、根据集合A中的name查询出集合B中对应的属性信息；
问题2、根据集合B中的属性信息（单个属性，如age<20等），查询出集合A中对应的name。

2.给出一个文件，里面包含两个字段{url、size}，
即url为网址，size为对应网址访问的次数，
要求：
问题1、利用Linux Shell命令或自己设计算法，
查询出url字符串中包含“baidu”子字符串对应的size字段值；
问题2、根据问题1的查询结果，对其按照size由大到小的排列。
（说明：url数据量很大，100亿级以上）

83.第3组百度面试题
1.今年百度的一道题目
百度笔试：给定一个存放整数的数组，重新排列数组使得数组左边为奇数，右边为偶数。
要求：空间复杂度O(1)，时间复杂度为O（n）。

2.百度笔试题
用C语言实现函数void * memmove(void *dest, const void *src, size_t n)。
memmove函数的功能是拷贝src所指的内存内容前n个字节到dest所指的地址上。
分析：
由于可以把任何类型的指针赋给void类型的指针
这个函数主要是实现各种数据类型的拷贝。

84.第4组百度面试题
2010年3道百度面试题[相信，你懂其中的含金量]
1.a~z包括大小写与0~9组成的N个数
用最快的方式把其中重复的元素挑出来。
2.已知一随机发生器，产生0的概率是p，产生1的概率是1-p，现在要你构造一个发生器，
使得它构造0和1的概率均为1/2；构造一个发生器，使得它构造1、2、3的概率均为1/3；...，
构造一个发生器，使得它构造1、2、3、...n的概率均为1/n，要求复杂度最低。
3.有10个文件，每个文件1G，
每个文件的每一行都存放的是用户的query，每个文件的query都可能重复。
要求按照query的频度排序.

85.又见字符串的问题
1.给出一个函数来复制两个字符串A和B。
字符串A的后几个字节和字符串B的前几个字节重叠。
分析：记住，这种题目往往就是考你对边界的考虑情况。
2.已知一个字符串，比如asderwsde,寻找其中的一个子字符串比如sde的个数，
如果没有返回0，有的话返回子字符串的个数。

86.
怎样编写一个程序，把一个有序整数数组放到二叉树中？
分析:本题考察二叉搜索树的建树方法，简单的递归结构。
关于树的算法设计一定要联想到递归，因为树本身就是递归的定义。

而，学会把递归改称非递归也是一种必要的技术。
毕竟，递归会造成栈溢出，关于系统底层的程序中不到非不得以最好不要用。
但是对某些数学问题，就一定要学会用递归去解决。

87.
1.大整数数相乘的问题。（这是2002年在一考研班上遇到的算法题）
2.求最大连续递增数字串（如“ads3sl456789DF3456ld345AA”中的“456789”）
3.实现strstr功能，即在父串中寻找子串首次出现的位置。
（笔试中常让面试者实现标准库中的一些函数）

88.2005年11月金山笔试题。编码完成下面的处理函数。
函数将字符串中的字符'*'移到串的前部分，

前面的非'*'字符后移，但不能改变非'*'字符的先后顺序，函数返回串中字符'*'的数量。
如原始串为：ab**cd**e*12，
处理后为*****abcde12，函数并返回值为5。（要求使用尽量少的时间和辅助空间）

89.神州数码、华为、东软笔试题
1.2005年11月15日华为软件研发笔试题。实现一单链表的逆转。
2.编码实现字符串转整型的函数（实现函数atoi的功能），据说是神州数码笔试题。如将字符
串 ”+123”123, ”-0123”-123, “123CS45”123, “123.45CS”123, “CS123.45”0
3.快速排序（东软喜欢考类似的算法填空题，又如堆排序的算法等）
4.删除字符串中的数字并压缩字符串。
如字符串”abc123de4fg56”处理后变为”abcdefg”。注意空间和效率。
（下面的算法只需要一次遍历，不需要开辟新空间，时间复杂度为O(N)）
5.求两个串中的第一个最长子串（神州数码以前试题）。
如"abractyeyt","dgdsaeactyey"的最大子串为"actyet"。

90.
1.不开辟用于交换数据的临时空间，如何完成字符串的逆序
(在技术一轮面试中，有些面试官会这样问)。
2.删除串中指定的字符
（做此题时，千万不要开辟新空间，否则面试官可能认为你不适合做嵌入式开发）
3.判断单链表中是否存在环。

91.
1.一道著名的毒酒问题
有1000桶酒，其中1桶有毒。而一旦吃了，毒性会在1周后发作。
现在我们用小老鼠做实验，要在1周内找出那桶毒酒，问最少需要多少老鼠。
2.有趣的石头问题
有一堆1万个石头和1万个木头，对于每个石头都有1个木头和它重量一样，
把配对的石头和木头找出来。

92.
1.多人排成一个队列,我们认为从低到高是正确的序列,但是总有部分人不遵守秩序。
如果说,前面的人比后面的人高(两人身高一样认为是合适的),
那么我们就认为这两个人是一对“捣乱分子”,比如说,现在存在一个序列:
176, 178, 180, 170, 171
这些捣乱分子对为
<176, 170>, <176, 171>, <178, 170>, <178, 171>, <180, 170>, <180, 171>,
那么,现在给出一个整型序列,请找出这些捣乱分子对的个数(仅给出捣乱分子对的数目即可,不用具体的对)

要求：
输入:
为一个文件(in)，文件的每一行为一个序列。序列全为数字，数字间用”,”分隔。
输出：
为一个文件(out)，每行为一个数字，表示捣乱分子的对数。

详细说明自己的解题思路，说明自己实现的一些关键点。
并给出实现的代码 ，并分析时间复杂度。
限制：
输入每行的最大数字个数为100000个，数字最长为6位。程序无内存使用限制。