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

2019-11-06 07:52:44

字体：大中小

来源：转载

供稿：网友

首先，我们复习一下链表的一些基本知识点： 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(); }}

上一篇：PP保护1:读写进程内存

下一篇：APUE读书笔记---进程间通信之POSIX共享内存区

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注