单链表倒转 （只遍历一次）

#include <iostream>
#include <iomanip>

using namespace std;

struct Node
{
      Node* next;
      int data;
};

struct Node* reverse(struct Node* head);

int main()
{
     Node* head = new Node;

     head->data = 0;
     head->next = NULL;

     Node* q = head;

     for(int i = 0; i < 10; ++i)
     {
             Node* tmp = new Node;
             tmp->data = i + 1;
             q->next = tmp;
             q = tmp;
    }

    q->next = NULL;

    Node *p = head;

    cout << "before : ";
    while(p)
    {
             cout << std::left << setw(2) << p->data << " ";
             p = p->next;
    }

    cout << endl;

    cout << "reverse: ";
    p = reverse(head);

    while(p)
    {
             cout << std::left << setw(2) << p->data << " ";
             p = p->next;
    }

    cout << endl;


    system("pause");
    return 0;
}

struct Node* reverse(struct Node* head)
{
      Node* p = head;
      Node* q = NULL;
      Node* r = NULL;

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

     return q;
}

结果如下：

before : 0  1  2  3  4  5  6  7  8  9  10
reverse: 10 9  8  7  6  5  4  3  2  1  0