链表反转

反转类型问题是面试中的常见问题。如反转字符串，反转链表等，今天给出利用递归和非递归方法解决反转链表问题的两个解决思路和代码：

非递归解法：

非递归来解决问题，用迭代的方法可以说思路是比较明确的。从头节点开始，依次用节点来表示当前节点和其指向的下一个节点，并且保存指向后续节点的指针，然后把节点间的指向关系进行反转。代码如下：（返回值使用Node*型主要是为了链式操作）

Node* reverseList(Node* head)
{
if(head == NULL || head->next == NULL) return NULL;
Node* p = head;
Node* q = head->next;
Node* r = NULL;

head->next = NULL;
while(q)
{
    r = q->next;
    q->next = p;
    p = q;
    q = r;
}
head = p;
return head;
}

递归解法：

递归的思路可谓非常巧妙。
（1）如果链表只有一个节点的话，反转整个链表相当于直接返回这个节点，没有节点直接返回；
（2）如果有很多个节点如1->2->3->4->5->6,那么反转的过程相当于反转1->l{}（其中集合l{}表示已经反转完成的剩下部分节点）
（3）然后递归反转l{}中的节点，直到到递归出口，即最后一个节点

采用递归的思路，代码就非常简洁：

Node * reverseListByRecursive(Node * head)
{
    if(head == NULL|| head->next == NULL) return head;
    Node *p = reverseListByRecuisive(head->next);

   head->next->next = head;
   head ->next = NULL;
   return p;
}

如果童鞋们在理解的时候觉得理解递归或者迭代有困难，可以先从比较基础的入门，如斐波那契数列的递归和非递归解决，也是几乎一样的想法。毕竟递归是很重要的设计思路，想明白递归才能更好地理解动态规划等其他重要的东西。