[转]链表的逆序实现

链表的头节点

1 struct ListNode
2 {
3       void*       m_nKey;
4       ListNode* m_pNext;
5 };

常规实现

代码

 ListNode* ReverseIteratively(ListNode* pHead)
{
      ListNode* pReversedHead = NULL;
      ListNode* pNode = pHead;
      ListNode* pPrev = NULL;
      while(pNode != NULL)
      {
            // get the next node, and save it at pNext
            ListNode* pNext = pNode->m_pNext;

            // if the next node is null, the currect is the end of original
            // list, and it's the head of the reversed list
            if(pNext == NULL)
                  pReversedHead = pNode;

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

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

递归实现(不需要临时节点)

代码

 1 ListNode* reverse_list( ListNode* head)       //逆序
 2  {
 3   ListNode* new_head=head;
 4  if(head==NULL || head->next==NULL)
 5   return head;
 6  new_head = reverse_list(head->next);
 7  head->next->next=head;
 8  head->next=NULL; //防止链表成为一个环，这是最关键的。
 9   return new_head; 
10 }