算法面试：链表转置

//单链表定义

class ListNode{
        int m_nValue;
        ListNode pNext;
};

普通的循环的方法。

//单链表逆置实现

ListNode ReverseList(ListNode pHead)
{
    if (pHead == NULL || pHead->pNext == NULL)
    {
        retrun pHead;
    }
  
    ListNode pRev = NULL;
    ListNode pCur = pHead;
    while(pCur != NULL)
    {
        ListNode pTemp = pCur;   // 步骤①
        pCur = pCur->pNext;       // 步骤②
        pTemp->pNext = pRev;      // 步骤③
        pRev = pTemp;
    }
    return pRev;
}

递归调用方法

ListNode ReverseList(ListNode pHead)
{
    ListNode p = NULL;
    if (pHead == NULL || pHead->pNext == NULL)
    {
        return pHead;
    } else {
        p = ReverseList(pHead -> pNext);
        p->pNext = pHead;
        pHead -> pNext = NULL;
    }
   
    return  pHead;
}