Implement the reversal of a singly linked list iteratively and recursively.

链表逆置既可以用迭代实现也可以使用递归实现。在我看来，迭代法应该比其递归形式的等价实现更加高效，内存开销更小。（试想对一个包含百万个元素的链表执行递归的逆置操作!很快栈空间就会用尽）

递归实现的代码行数更少，但是要想把代码写对会比较困难。另一方面，迭代实现代码行数较多但是比较容易验证。

1) 迭代实现:

void reverse(Node*& head) {
  if (!head) return;
  Node* prev = NULL;
  Node* curr = head;
  while (curr) {
    Node* next = curr->next;
    curr->next = prev;
    prev = curr;
    curr = next;
  }
  head = prev;
}

请一定要注意头指针是引用传递。如果你理解这个语法有困难，将指针看成一种类型，类型后加一个&符号表示变量是引用传递。如果头指针本身有可能会改变，那么就一定要使用引用传递。

2) 递归实现:

void reverse(Node*& p) {
  if (!p) return;
  Node* rest = p->next;
  if (!rest) return;
  reverse(rest);
  p->next->next = p;
  p->next = NULL;
  p = rest;
}

你能看懂为什么头节点最终指向了原链表的最后一个元素吗？尝试画一个图，看看递归退出时rest指针是怎样变化的。

原文链接：http://leetcode.com/2010/04/reversing-linked-list-iteratively-and.html

本文链接：http://bookshadow.com/weblog/2015/01/31/cpp-singly-linked-list-reverse-iterative-recursive/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码