【剑指offer】面试题5：链表-从尾到头打印链表

首先，我们复习一下链表的一些基本知识点： 1.创建 2.插入 3.删除

struct ListNode { int m_nValue; ListNode*m_pNext; }; //往链表中插入一个结点 void AddToTail(ListNode** pHead, int value)//传入二级指针，是因为可能修改头指针,一级指针只能修改形参 { ListNode* pNew = new ListNode(); pNew->m_nValue = value; pNew->m_pNext = NULL; if (*pHead == NULL) { *pHead = pNew; } else { ListNode*pCur = *pHead; while (pCur->m_pNext != NULL) { pCur = pCur->m_pNext; } pCur->m_pNext = pNew; } }

在链表中找到第一个含某值的结点并删除该结点

void RemoveNode(ListNode** pHead,int value)//删除结点一定要注意空间的释放 { if (pHead==NULL||*pHead == NULL) { return; } ListNode* pToDeleted = NULL; if ((*pHead)->m_nValue == value) { pToDeleted = *pHead; *pHead = (*pHead)->m_pNext; } else { ListNode *pNode = *pHead; while (pNode->m_pNext != NULL&&pNode->m_pNext->m_nValue != value)//最坏情况是遍历完链表,用下一个结点来进行判断是因为方便后续的删除 { pNode = pNode->m_pNext; } //删除找到的结点 if ((pNode->m_pNext != NULL) && (pNode->m_pNext->m_nValue = value)) { pToDeleted = pNode->m_pNext; pNode->m_pNext = pNode->m_pNext->m_pNext; } } if (pToDeleted != NULL) { delete pToDeleted; pToDeleted = NULL; } }

面试题5：从尾到头打印链表

//输入一个链表的头结点，从尾到头反过来打印出每个结点的值 //思路：遍历的顺序是从头到尾遍历，可输出的顺序却是从尾到头，也就是说第一个遍历的结点最后一个输出，最后一个遍历的结点却第一个输出 //这是典型的先入后出的方式，我们可以用栈来实现这种顺序，每经过一个结点的时候，把该节点放到一个栈中，当遍历完整个链表后，再从栈顶开始输出每个结点的值，这是顺出的顺序就实现了反转 void PRintListReverseingly_Iteratively(ListNode* pHead) { std::stack<ListNode*> nodes; ListNode*pNode = pHead; //压栈 while (pNode != NULL) { nodes.push(pNode); pNode = pNode->m_pNext; } //出栈 while (!nodes.empty()) { pNode = nodes.top();//取出栈顶元素 printf("%d\t", pNode->m_nKey); nodes.pop(); } }