数学答题（一）单向链表反转
0 如何分析数学问题
大部分问题是数学问题，代码只是表示数学问题的一种有效方式。在遇到一个待解决的问题时，先从数学的角度考虑这个问题，已知条件是什么？给定的已知条件有什么性质可用？处理一般情况的步骤？特殊情况是什么？分析好这些问题，然后在入手写代码。下面以链表反转为例。
面试题：定义一个函数，输入一个单向链表的头节点，反转该链表并输出反转链表的头节点。链表节点定义如下：
Class Link{
int key;
Link next;
}
1 已知条件
已知单链表，那么单链表有哪些性质可用？
性质1：链表是已知头节点的
性质2：单向链表能够从一个节点知道下一个节点，next=current.next （即图中B->C）
性质3：单向链表的尾节点的下个节点是null，更具这个性质我们常常遍历单向链表，结束条件是current==null
2 分析问题
从问题的结果考虑，以上图为例，我们希望反转后链表中
A<-B，
而先前是A->B
所以我们需要在遍历节点的时候保存节点A和B的信息，然后将B->A。 但是B->A后，无法再根据B找到C（因为我们已经将B的下一个节点指向了A），因此，无法再循环遍历下去。所以在改变B->A之前，需要保存B->C的信息。至此，我们需要3个指针指向A,B,C来保存其处理前的信息，如下图（这里用到了性质2和性质3）
现在，我们总结下处理该问题的步骤：
step1: 保存3个节点的信息
previous=current
current=current.next
next=current.next
step2: 节点反转
current.next=previous
current=next
step3: 循环步骤1和2
循环结束条件current==null （性质3）
step4: 循环结束后处理原来的头节点
first.next=null
step5: 返回反转后链表的头节点
即previous，因为循环结束后current为null,则前一个节点previous为反转后的头节点
3 特殊情况
现在我们要返回头看下上述解决问题的步骤，我们发现解决该问题，必须要先满足以下条件：即链表中要存在多于2个节点，才能有3个指针指向A,B,C。
那么根据这个一般情况条件，我们可以得出如下的特殊情况：
1）链表为空
2）链表只有1个节点
3）链表只有2个节点
4 代码实现
4.1 先写出代码框架
在写具体代码写，先写出代码框架，有助于问题的发现和解决，并减少错误
public Link reverseList(LinkedList list, Link firstLink) {
// sepecial case
if (list == null)
return null;
// list have only one node
if (firstLink.next == null)
return firstLink;
// initial three pointer
Link previous = null;
Link current = firstLink;
Link next = current.next;
// list have only two node
if (next == null) {
//TODO
}// end if
// list have more than two nodes
while (current != null) {
// step1: keep three pointer
// previous=current
// current=current.next
// next=current.next
// step2: reverse
// current.next=previous
// current=next
//TODO
}// end while
// step4: make first as the last pointer first.next=null
firstLink.next=null;
// step5: return the firstLike after reverse TODO
}// end reverseList
4.2 其次写出代码测试用例
写出测试用例，对后面的代码解析测试
// test case
// list is null
// list have only one node
// list have only two nodes
// list have more than two nodes
4.3 最后才是代码具体实现
public Link reverseList(LinkedList list, Link firstLink) {
// sepecial case
if (list == null)
return null;
// list have only one node
if (firstLink.next == null)
return firstLink;
// initial three pointer
Link previous = null;
Link current = firstLink;
Link next = current.next;
// list have only two node
if (next == null) {
current.next=previous;
firstLink.next=null;
return current;
}// end if
// list have more than two nodes
while (current != null) {
//reverse
current.next=previous;
current=next;
// keep three pointer
previous=current;
current=current.next;
next=current.next;
}// end while
// step4: make first as the last pointer first.next=null
firstLink.next=null;
// step5: return the firstLike after reverse
return previous;
}// end reverseList