链表反转
单向链表的反转是一个经常被问到的一个面试题，也是一个非常基础的问题。比如一个链表是这样的： 1->2->3->4->5 通过反转后成为5->4->3->2->1。最容易想到的方法遍历一遍链表，利用一个辅助指针，存储遍历过程中当前指针指向的下一个元素，然后将当前节点元素的指针反转后，利用已经存储的指针往后面继续遍历。源代码如下：
单向链表的反转是一个经常被问到的一个面试题，也是一个非常基础的问题。比如一个链表是这样的： 1->2->3->4->5 通过反转后成为5->4->3->2->1。最容易想到的方法遍历一遍链表，利用一个辅助指针，存储遍历过程中当前指针指向的下一个元素，然后将当前节点元素的指针反转后，利用已经存储的指针往后面继续遍历。源代码如下：
给定两个排好序的数组，怎样高效得判断这两个数组中存在相同的数字？
这个问题首先想到的是一个O(nlogn)的算法。就是任意挑选一个数组，遍历这个数组的所有元素，遍历过程中，在另一个数组中对第一个数组中的每个元素进行binary search。用C++实现代码如下：
问题：
给定一整数序列A1， A2，... An （可能有负数），求A1~An的一个子序列Ai~Aj，使得Ai到Aj的和最大
例如：
整数序列-2, 11, -4, 13, -5, 2, -5, -3, 12, -9的最大子序列的和为21。
对于这个问题，最简单也是最容易想到的那就是穷举所有子序列的方法。利用三重循环，依次求出所有子序列的和然后取最大的那个。当然算法复杂度会达到O(n^3)。显然这种方法不是最优的，下面给出一个算法复杂度为O(n)的线性算法实现，算法的来源于Programming Pearls一书。
这道题和解判断链表是否存在环，我用的是非常类似的方法，只不过结束循环的条件和函数返回值不一样罢了。设置两个指针p1，p2。每次循环p1向前走一步，p2向前走两步。当p2到达链表的末尾时，p1指向的时链表的中间。
link* mid(link* head)
{
link* p1,*p2;
p1=p2=head;
if(head==NULL || head->next==NULL)
return head;
do {
p1=p1->next;
p2=p2->next->next;
} while(p2 && p2->next);
return p1;
}
并不是简单的字符串反转，而是按给定字符串里的单词将字符串倒转过来，就是说字符串里面的单词还是保持原来的顺序，这里的每个单词用空格分开。例如：
Here is www.zhuxinquan.com
经过反转后变为：
www.zhuxinquan.com is Here
如果只是简单的将所有字符串翻转的话，可以遍历字符串，将第一个字符和最后一个交换，第二个和倒数第二个交换，依次循环。其实按照单词反转的话可以在第一遍遍历的基础上，再遍历一遍字符串，对每一个单词再反转一次。这样每个单词又恢复了原来的顺序。
问题：判断一个链表是否存在环，例如下面这个链表就存在一个环：
例如N1->N2->N3->N4->N5->N2就是一个有环的链表，环的开始结点是N5
这里有一个比较简单的解法。设置两个指针p1，p2。每次循环p1向前走一步，p2向前走两步。直到p2碰到NULL指针或者两个指针相等结束循环。如果两个指针相等则说明存在环。
struct link {
int data;
link* next;
};
bool IsLoop(link* head)
{
link* p1=head, *p2 = head;
if (head ==NULL || head->next ==NULL) {
return false;
}
do{
p1= p1->next;
p2 = p2->next->next;
} while(p2 && p2->next && p1!=p2);
if(p1 == p2)
return true;
else
return false;
}
问题：一个动态长度可变的数字序列，以数字0为结束标志，要求将重复的数字用一个数字代替，例如：
将数组 1,1,1,2,2,2,2,2,7,7,1,5,5,5,0 转变成1,2,7,1,5,0
问题比较简单，要注意的是这个数组是动态的。所以避免麻烦我还是用了STL的vector。
我没有记错的话是一道MSN的笔试题，网上无意中看到的，拿来做了一下。题目是这样的，给定一个字符串，一个这个字符串的子串，将第一个字符串反转，但保留子串的顺序不变。例如：
输入： 第一个字符串: "This is zhuxinquan's Chinese site: http://www.zhuxinquan.com/cn"
子串: "zhuxinquan"
输出： "nc/moc.zhuxinquan.www//:ptth :etis esenihC s'zhuxinquan si sihT"
一般的方法是先扫描一边第一个字符串，然后用stack把它反转，同时记录下子串出现的位置。然后再扫描一遍把记录下来的子串再用stack反转。我用的方法是用一遍扫描数组的方法。扫描中如果发现子串，就将子串倒过来压入堆栈。
最后再将堆栈里的字符弹出，这样子串又恢复了原来的顺序。源代码如下：
问题：判断一个二叉排序树是否是平衡二叉树
这里是二叉排序树的定义
解决方案：
根据平衡二叉树的定义，如果任意节点的左右子树的深度相差不超过1，那这棵树就是平衡二叉树。
首先编写一个计算二叉树深度的函数，利用递归实现。
template<typename T>
static int Depth(BSTreeNode<T>* pbs)
{
if (pbs==NULL)
return 0;
else
{
int ld = Depth(pbs->left);
int rd = Depth(pbs->right);
return 1 + (ld >rd ? ld : rd);
}
}
下面是利用递归判断左右子树的深度是否相差1来判断是否是平衡二叉树的函数：
template<typename T>
static bool isBalance(BSTreeNode<T>* pbs)
{
if (pbs==NULL)
return true;
int dis = Depth(pbs->left) - Depth(pbs->right);
if (dis>1 || dis<-1 )
return false;
else
return isBalance(pbs->left) && isBalance(pbs->right);
}
static const char* _strstr(const char* s1, const char* s2)
{
assert(s2 && s1);
const char* p=s1, *r=s2;
while(*p!='\0')
{
while(*p++==*r++);
if(*r=='\0')
return p;
else
{
r=s2;
p=++s1;
}
}
return NULL;
}