学步园

template<typename T><br /> struct Node<br /> {<br /> Node(T v):val(v), next(NULL) {}<br /> T val;<br /> Node *next;<br /> };</p> <p>template<typename T><br /> Node<T> *listReverseIteratively(Node<T> *head)<br /> {<br /> Node<T> *lp = NULL;<br /> Node<T> *rp = head;<br /> while(rp != NULL)<br /> {<br /> Node<T> *temp = rp->next;<br /> rp->next = lp;<br /> lp = rp;<br /> rp = temp;<br /> }<br /> return lp;<br /> }</p> <p>template<typename T><br /> Node<T> *listReverse(Node<T> *head)<br /> {<br /> Node<T> *np = NULL;<br /> return listReverse_imp(np, head);<br /> }</p> <p>template<typename T><br /> Node<T> *listReverse_imp(Node<T> *lp, Node<T> *rp)<br /> {<br /> if (rp != NULL)<br /> {<br /> Node<T> *temp = rp->next;<br /> rp->next = lp;<br /> return listReverse_imp(rp, temp);<br /> }<br /> else<br /> return lp;<br /> }<br />

迭代与递归方式

口<-口<-口 口->口->口

             ^  ^

              |   |

              lp  rp