单链表逆序

    实现一：

#include "stdafx.h" <br>
#include <iostream> <br>
using namespace std; <br><br>
template <typename T> <br>
struct MyNode <br>
{ <br>
T id; <br>
MyNode * next; <br>
MyNode(T _id) <br>
{ <br>
id = _id; <br>
next = NULL; <br>
} <br>
}; <br><br>
template <typename T> <br>
class MyList <br>
{ <br>
MyNode<T> * head; <br>
MyNode<T> * current; <br>
public: <br>
MyList() : head(NULL) {} <br>
void add(T value) <br>
{ <br>
MyNode<T>* node = new MyNode<T>(value); <br>
if(head == NULL) <br>
{ <br>
head = node; <br>
current = head; <br>
} <br>
else <br>
{ <br>
current->next = node; <br>
current = node; <br>
} <br>
} <br>
void showAll() <br>
{ <br>
MyNode<T> *go = head; <br>
while(go != NULL) <br>
{ <br>
cout<<go->id<<endl; <br>
go = go->next; <br>
} <br><br>
} <br>
void reverse() <br>
{ <br>
MyNode<T> *preNode = NULL; <br>
MyNode<T> *currentNode = head; <br>
MyNode<T> *nextNode = head->next; <br>
while(true) <br>
{ <br>
nextNode = currentNode->next; <br>
currentNode->next = preNode; <br>
preNode = currentNode; <br>
currentNode = nextNode; <br>
if(currentNode->next == NULL) <br>
{ <br>
head = currentNode; <br>
head->next = preNode; <br>
break; <br>
} <br>
} <br>
} <br>
}; <br><br><br>
int main(int argc, char * argv[]) <br>
{ <br>
MyList<int> *list = new MyList<int>(); <br>
list->add(123); <br>
list->add(456); <br>
list->add(789); <br>
list->showAll(); <br>
list->reverse(); <br>
cout<<"after reverse:"<<endl; <br>
list->showAll(); <br>
system("pause"); <br>
return 0; <br>
}

实现二：

#include<iostream><br>
#include<conio.h><br>
#include<list><br>
using namespace std;

template<class T><br>
struct Node{<br>
T value;<br>
struct Node<T>* next;<br>
Node(const T&amp; v):value(v),next(NULL){}<br>
~Node(){<br>
delete next;<br>
next=NULL;<br>
cout<<"~Node()"<<endl;<br>
}<br>
};

template<class T,class N><br>
class Iterator{<br>
public:<br>
Iterator(T v=NULL):t(v){}<br>
T&amp; operator++()const{<br>
t=t->next;<br>
return t;<br>
}<br>
const N&amp; operator*()const{<br>
return t->value;<br>
}<br>
N&amp;operator*(){<br>
return t->value;<br>
}<br>
const T&amp; getT()const{<br>
return t;<br>
}<br>
Iterator&amp; operator=(Iterator&amp; other){<br>
t=other.getT();<br>
return *this;<br>
}<br>
const Iterator&amp; operator=(Iterator&amp; other)const{<br>
t=other.getT();<br>
return *this;<br>
}<br>
private:<br>
mutable T t;<br>
};

template<class T,class N><br>
bool operator!=(Iterator<T,N> i1,Iterator<T,N> i2){<br>
return i1.getT()!=i2.getT();<br>
}

<br>
template<class T><br>
class NList{<br>
public:<br>
typedef Iterator<Node<T>*,T> iterator;<br>
typedef const Iterator<Node<T>*,T> const_iterator;<br>
NList(const T&amp; value){<br>
head=tail=new Node<T>(value);<br>
}<br>
void addNode(const T&amp; value){<br>
tail->next=new Node<T>(value);<br>
tail=tail->next;<br>
}<br>
iterator begin(){<br>
return iterator(head);<br>
}<br><br>
iterator end(){<br>
return iterator(tail->next);<br>
}<br>
void reverse(){<br>
if(head==tail)<br>
return ;<br>
Node<T>* end=head,*begin=tail;<br>
Node<T>* p1=head,*p2,*p3;<br>
p2=p1->next;<br>
p1->next=NULL;<br>
while(p2!=tail){<br>
p3=p2->next;<br>
p2->next=p1;<br>
p1=p2;<br>
p2=p3;<br>
}<br>
p2->next=p1;<br>
head=begin,tail=end;<br>
}<br>
~NList(){<br>
delete head;<br>
head=NULL;<br>
tail=NULL;<br>
cout<<"~NList()"<<endl;<br>
}<br>
private:<br>
Node<T>* head;<br>
Node<T>* tail;<br>
};

<br>
int main(){<br>
NList<int> nlist(1);<br>
nlist.addNode(2);<br>
nlist.addNode(3);<br>
NList<int>::const_iterator p=nlist.begin(),end=nlist.end();<br>
for(p=nlist.begin();p!=end;++p)<br>
cout<<*p<<endl;<br>
nlist.reverse();<br>
end=nlist.end();<br>
for(p=nlist.begin();p!=end;++p)<br>
cout<<*p<<endl;<br>
getch();<br>
return 0;<br>
}