算法27(反转链表)

http://blog.csdn.net/passball/article/details/6126658
链表结构的反转，基本上把基本链表的内容都做了一遍。

比如，基本链表的创建，链表的遍历，然后就是反转链表了。

链表结构如下：

a->b->c->d->e->NULL

弄三个指针head，mid,last，设置初值：

head指向a

mid指向NULL

然后开始指针运动了：

while(head != NULL)

{

last=mid;

mid=head;

head=head->next;

mid->next=last;

}

//last往mid走，mid往head走，head往head->next走，它们一直向前走，边走边mid->next=last，直到head==NULL为止。

 

第24题：反转链表
pPrev<-pNode<-pNext

ListNode* ReverseIteratively(ListNode* pHead)
{
ListNode* pReversedHead = NULL;
ListNode* pNode = pHead;
ListNode* pPrev = NULL;
while(pNode != NULL) //pNode<=>m
{
ListNode* pNext = pNode->m_pNext; //n保存在pNext下

//如果pNext指为空，则当前结点pNode设为头。
if(pNext == NULL)
pReversedHead = pNode;

// reverse the linkage between nodes
pNode->m_pNext = pPrev;

// move forward on the the list
pPrev = pNode;
pNode = pNext;
}
return pReversedHead;
}

或者，这样写：
head->next -> p-> q

template<class T>
Node<T>* Reverse(Node<T>* head)
{
p=head->next;
while(p)
{
q=p->next; //p->next先保存在q下
p->next=head->next; //p掉头指向head->next
head->next=p; //p赋给head->next
p=q; //q赋给p。
//上俩行即，指针前移嘛...
}
return head;