一、如何判断链表中有无环
解法：设置了两个指针p和q，他们分别以速度为1和2前进（公式应该是p和q分别以速度为v1和v2且|v2-v1|为1），如果到某一次循环发现他们相等，即都指向同一结点（空节点除外，以后讨论的节点都不包含空节点），则说明这个单向链表中存在循环。否则就是没有循环。
二、最大子序列问题：给定一整数序列A1， A2，... An （可能有负数），求A1~An的一个子序列Ai~Aj，使得Ai到Aj的和最大
解法：运用动态规划的思想，才能达到线性复杂度
//线性的算法O(N)
long maxSubSum4(const vector<int>& a)
{
long maxSum = 0, thisSum = 0;
for (int j = 0; j < a.size(); j++)
{
thisSum += a[j];
if (thisSum > maxSum)
maxSum = thisSum;
else if (thisSum < 0)
thisSum = 0;
}
return maxSum;
}
三、如何判断一棵二叉树是否是平衡二叉树
解法：根据平衡二叉树的定义，如果任意节点的左右子树的深度相差不超过1，那这棵树就是平衡二叉树。
那怎样才能达到线性复杂度呢？这里运用
动态规划
的思想
那怎样才能达到线性复杂度呢？这里运用
动态规划
的思想
原文：http://muyunzhe.blog.51cto.com/9164050/1669563