题1 链表反转

综述：

   最近偶尔上网上看看算法的题目，感觉做一个IT，不能只顾业务代码，偶尔学学算法，提高下自己的思维。不然总是思维定势，有时候感觉找不到方向。

题目：

   链表反转，要求用递归和非递归两种方式实现。

分析：

   链表是大家都经常用到的一个数据结构。在C++stl里面经常会用到，首先我们使用数学归纳法来实现递归的实现，数学归纳法，也就是假设我们已经把前
n-1个数据实现了反转，然后第n个，我们直接把第n个指向前n-1个，然后递归n+1就行了，然后我们注意递归的终止条件，也就是当前节点不为空。
 我们首先定义数据结构：

template<class Type>
struct ListNode{ListNode *next; Type value;};

然后我们定义我们的函数：

1.先递归再反转

我们从链表结尾往前反转，先压栈然后根据栈的信息反转。

template<class Type>
ListNode* RevertList(ListNode* node)
{
     if(!node || !node->next)//如果链表为空，或者超出链表返回，我们需要给一个递归终止点，也就是反转后的链表头
      return node;
    ListNode* tmp = RevertList(node->next);//我们假设反转了,返回已经反转的链表尾部
    tmp->next = node;
       node->next = NULL;
       return node;
}

2.先反转再递归

我们也可以一边反转一边递归，也就是假设我们反转到节点A，他前面的已经反转成功，我们把A指向他前面的反转成功的第一个节点，也就是他的父节点，
因为我们无法知道他的父节点，所以得通过参数传递下来。

template<class Type>
void RevertList(ListNode<Type>* node, ListNode<Type>*prev)//我们得传递前面的一个节点，第一次调用可以prev=NULL
{
   if(!node)//节点为空，或者已经到达尾部
       return;
   ListNode<Type> *tmp = node->next;//保存住该节点的下一个节点递归用
   node->next = prev;
   RevertList(tmp, node);
}

3.迭代算法

  假设我们有A，B，C ，其中A-〉B-〉C。我们首先指向A，把A指向他的前一个节点此时为NULL，但是我们得保存它，然后我们也得保存A-〉next也就是B，不然就丢失了B，所以我们得用一个临时变量，保存B。所以加上本身总共3个节点变量。

template<class Type>
void RevertList(ListNode<Type>*node)
{
   if(!node || !node->next)
      return node;
   ListNode<Type> *prev = NULL,
                  *next = NULL;
   while(node)
   {
     next = node->next;//保存住本节点的下一个节点
     node->next = prev;//本节点指向前一个节点
     prev = node;//为下次循环做准备，往后移动一个节点
     node = next;
   }

}

综述：

 得时常回顾这些算法，不然自己想确实会遗忘很多边边角角的东西。例如边界啥的。