剑指offer--面试题16

时间:2022-04-11 01:49:07
#include<stack>

//思路:遍历链表过程中,将各个指针入栈,再出栈进行反转
ListNode* ReverseList(ListNode* pHead)
{
if(pHead == NULL)
return NULL;
ListNode* pNode = pHead; stack<ListNode*> pNodeStack;
while(pNode != NULL)
{
pNodeStack.push(pNode);
pNode = pNode->m_pNext;
} pNode = pNodeStack.top();
ListNode* pFront = pNode;
pNodeStack.pop(); while(!pNodeStack.empty())
{
pNode->m_pNext = pNodeStack.top();
pNode = pNode->m_pNext;
pNodeStack.pop();
} pNode->m_pNext = NULL; return pFront;
}

不用栈,自己还真不好编。。。

虽然有思路,但写出代码来还比较困难。。。惊叹于作者代码的精炼!!!

学习:

ListNode* ReverseList(ListNode* pHead)
{
ListNode* pReversedHead = NULL;
ListNode* pNode = pHead;
ListNode* pPrev = NULL;
while(pNode != NULL)
{
ListNode* pNext = pNode->m_pNext; if(pNext == NULL)
pReversedHead = pNode; pNode->m_pNext = pPrev; pPrev = pNode;
pNode = pNext;
} return pReversedHead;
}