template<typename T>
Node<T> *listReverseIteratively(Node<T> *head)
{
Node<T> *lp = NULL;
Node<T> *rp = head;
while(rp != NULL)
{
Node<T> *temp = rp->next;
rp->next = lp;
lp = rp;
rp = temp;
}
return lp;
}
template<typename T>
Node<T> *listReverse(Node<T> *head)
{
Node<T> *np = NULL;
return listReverse_imp(np, head);
}
template<typename T>
Node<T> *listReverse_imp(Node<T> *lp, Node<T> *rp)
{
if (rp != NULL)
{
Node<T> *temp = rp->next;
rp->next = lp;
return listReverse_imp(rp, temp);
}
else
return lp;
}
迭代与递归方式
口<-口<-口 口->口->口
^ ^
| |
lp rp