结语：
单链表只有一个向前指针Next，所以要使用1-2个额外变量来存储当前元素的前一个或后一个指针。
尽量用while循环而不要用for循环，来进行遍历。 哇塞，我就是不用指针，照样能“修改地址”，达到和C++同样的效果，虽然很烦~
遍历的时候，不要在while循环中head=head.Next;这样会改变原先的数据结构。我们要这么写：Link curr=head;然后curr=curr.Next;
有时我们需要临时把环切开，有时我们需要临时把单链表首尾相连成一个环。 究竟是玩curr还是curr.Next，根据不同题目而各有用武之地，没有定论，不必强求。
二、栈和队列
目录：
1.设计含min函数的栈，要求min、push和pop的时间复杂度都是o(1)。 2.设计含min函数的栈的另解 3.用两个栈实现队列 4.用两个队列实现栈
5.栈的push、pop序列是否一致
6.递归反转一个栈，要求不得重新申请一个同样的栈，空间复杂度o(1) 7.给栈排个序
8..如何用一个数组实现两个栈 9..如何用一个数组实现三个栈
1.设计含min函数的栈，要求min、push和pop的时间复杂度都是o(1)。
算法思想：需要设计一个辅助栈，用来存储当前栈中元素的最小值。网上有人说存储当前栈中元素的最小值的所在位置，虽然能节省空间，这其实是不对的，因为我在调用Min函数的时候，只能得到位置，还要对存储元素的栈不断的pop，才能得到最小值——时间复杂度o(1)。 所以，还是在辅助栈中存储元素吧。
此外，还要额外注意Push操作，第一个元素不用比较，自动成为最小值入栈。其它元素每次都要和栈顶元素比较，小的那个放到栈顶。
public class NewStack {
private Stack dataStack; private Stack mindataStack; public NewStack() {
dataStack = new Stack(); mindataStack = new Stack(); }
public void Push(int element) {
dataStack.Push(element); if (mindataStack.Count == 0)
mindataStack.Push(element);
else if (element <= (int)mindataStack.Peek()) mindataStack.Push(element); else //(element > mindataStack.Peek)
mindataStack.Push(mindataStack.Peek()); }
public int Pop() {
if (dataStack.Count == 0)
throw new Exception(\
mindataStack.Pop();
return (int)dataStack.Pop(); }
public int Min() {
if (dataStack.Count == 0)
throw new Exception(\
return (int)mindataStack.Peek(); } }
2.设计含min函数的栈的另解
话说，和青菜脸呆久了，就沾染了上海小市民意识，再加上原本我就很抠门儿，
于是对于上一题目，我把一个栈当成两个用，就是说，每次push，先入站当前元素，然后入栈当前栈中最小元素；pop则每次弹出2个元素。
算法代码如下所示（这里最小元素位于当前元素之上，为了下次比较方便）： public class NewStack {
private Stack stack; public NewStack() {
stack = new Stack(); }
public void Push(int element) {
if (stack.Count == 0) {
stack.Push(element); stack.Push(element); }
else if (element <= (int)stack.Peek()) {
stack.Push(element); stack.Push(element); }
else //(element > stack.Peek) {
object min = stack.Peek(); stack.Push(element);
stack.Push(min); } }
public int Pop() {
if (stack.Count == 0)
throw new Exception(\stack.Pop();
return (int)stack.Pop(); }
public int Min() {
if (stack.Count == 0)
throw new Exception(\return (int)stack.Peek(); } }
之所以说我这个算法比较叩门，是因为我只使用了一个栈，空间复杂度o(N)，节省了一半的空间（算法1的空间复杂度o(2N)）。
3.用两个栈实现队列
实现队列，就要实现它的3个方法：Enqueue（入队）、Dequeue（出队）和Peek（队头）。
1）stack1存的是每次进来的元素，所以Enqueue就是把进来的元素push到stack1中。
2）而对于Dequeue，一开始stack2是空的，所以我们把stack1中的元素全都pop到stack2中，这样stack2的栈顶就是队头。只要stack2不为空，那么每次出队，就相当于stack2的pop。
3）接下来，每入队一个元素，仍然push到stack1中。每出队一个元素，如果stack2不为空，就从stack2中pop一个元素；如果stack2为空，就重复上面的操作——把stack1中的元素全都pop到stack2中。
4）Peek操作，类似于Dequeue，只是不需要出队，所以我们调用stack2的Peek操作。当然，如果stack2为空，就把stack1中的元素全都pop到stack2中。 5）注意边界的处理，如果stack2和stack1都为空，才等于队列为空，此时不能进行Peek和Dequeue操作。 按照上述分析，算法实现如下： public class NewQueue {
private Stack stack1; private Stack stack2; public NewQueue() {
stack1 = new Stack(); stack2 = new Stack(); }
public void Enqueue(int element) {
stack1.Push(element); }
public int Dequeue() {
if (stack2.Count == 0) {
if (stack1.Count == 0)
throw new Exception(\
else
while (stack1.Count > 0)
stack2.Push(stack1.Pop()); }
return (int)stack2.Pop(); }
public int Peek() {
if (stack2.Count == 0) {
if (stack1.Count == 0)
throw new Exception(\ else
while (stack1.Count > 0)
stack2.Push(stack1.Pop()); }
return (int)stack2.Peek(); } }
4.用两个队列实现栈
这个嘛，就要queue1和queue2轮流存储数据了。这个“轮流”发生在Pop和Peek的时候，假设此时我们把所有数据存在queue1中（此时queue2为空），我们把queue1的n-1个元素放到queue2中，queue中最后一个元素就是我们想要pop的元素，此时queue2存有n-1个元素（queue1为空）。
至于Peek，则是每次转移n个数据，再转移最后一个元素的时候，将其计下并返回。
那么Push的操作，则需要判断当前queue1和queue2哪个为空，将新元素放到不为空的队列中。 public class NewStack {
private Queue queue1; private Queue queue2; public NewStack() {
queue1 = new Queue(); queue2 = new Queue(); }
public void Push(int element) {
算法大全-面试题-数据结构
