C++算法题：关于链表的算法

单向链表节点结构：

struct ListNode  
{  
    int key;  
    ListNode *next;  
    ListNode(int k = 0, ListNode *p = NULL) { key = k; next = p;}  
}; 

ListNode* ReverseList(ListNode *pHead)  
{  
    ListNode *pPre = NULL;  
    ListNode *pCur = pHead;  
  
    //新的列表头结点要 pCur->next = pPre;pPre = pCur;
    //因为弹出一个节点后，要复原原链表所以要记录 ListNode *pNext = pCur->next;
    //开始反转  
    while(pCur != NULL)  
    {  
        ListNode *pNext = pCur->next; //临时保存下一个结点  
          
        //关键的三步，一次只返转一个元素，步子不要迈太大  
        pCur->next = pPre;  //反转  
        pPre = pCur;        //保存上一个结点  
        pCur = pNext;       //更新当前结点  
    }  
    return pPre;  //pPre变为第一个结点  
}  

栈实现, 栈后进先出

void ReorderPrint_Solution1(ListNode * pHead)  
{  
    stack keyStack;  //结点的数据栈    
    ListNode *pNode = pHead;  
  
    while(pNode != NULL)  //将链表的数据压栈  
    {  
        keyStack.push(pNode->key);  
        pNode = pNode->next;  
    }  
    while(keyStack.size() > 0) //出栈  
    {  
        cout< 
递归实现 倒序
 
void ReorderPrint_Solution2(ListNode * pHead)  
{  
    if(pHead == NULL)  
        return;  
    else  
    {  
        ReorderPrint_Solution2(pHead->next);  
// 打印节点值要放在后面
        cout<key<<' ';  
    }  
} 
 
 
问题3：给定链表的头指针和一个结点指针，在O(1)时间删除该结点。 
ListNode* DeleteNode(ListNode* pHead, ListNode* pDeleted)  
{  
    if(pHead == NULL || pDeleted == NULL)  
        return NULL;  
  
    if(pDeleted->next != NULL) //不是最后一个结点  
    {  

        ListNode *pNext = pDeleted->next; //删除的其实是下一个结点  
        //下面两步是关键  
        pDeleted->key = pDeleted->next->key;  
        pDeleted->next = pDeleted->next->next;  
        delete pNext;  
        pNext = NULL;  
    }  
    else    
    {  

        if(pHead == pDeleted) 
        {  
            pHead = NULL;  
        }  
        else  
        {  

            ListNode *pNode = pHead;  
            while(pNode->next != pDeleted) //找删除结点的前驱  
                pNode = pNode->next;  
            pNode->next = pDeleted->next;  
        }  
        delete pDeleted;  
        pDeleted = NULL;  
    }  
    return pHead;  
}