淘宝网站怎么做网站,建设项目环境影响评价验收网站,网站怎么做内链,建设项目自主验收公示网站记录来自《剑指offer》的算法题目 链表应该是面试时被提及最频繁的数据结构#xff0c;它的结构简单#xff0c;由若干个结点连接成链状结构#xff0c;其创建、插入结点、删除结点等操作都只需要20行左右的代码就能实现#xff0c;其代码量比较适合面试。
假设单链表的结…记录来自《剑指offer》的算法题目 链表应该是面试时被提及最频繁的数据结构它的结构简单由若干个结点连接成链状结构其创建、插入结点、删除结点等操作都只需要20行左右的代码就能实现其代码量比较适合面试。
假设单链表的结点定义如下
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* pNode *pHead;while (pNode-m_pNext ! NULL)pNode pNode-m_pNext;pNode-m_pNext pNew;}
}
这里第一个参数pHead是一个指向指针的指针因为在往一个空链表插入一个结点时这个结点就是链表的头指针也就是会改动头指针因此必须把pHead参数设为指向指针的指针否则出了这个函数pHead仍然是空指针。其测试代码如下
int main(void){ListNode* t NULL;for (int i 0; i 10;i)AddToTail(t, i);return 0;
}
删除某个结点的代码如下
// 删除给定数值的结点
void RemoveNode(ListNode** pHead, int value){if (pHead NULL || *pHead NULL)return;ListNode* pToBeDeleted NULL;if ((*pHead)-m_nValue value){pToBeDeleted *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){pToBeDeleted pNode-m_pNext;pNode-m_pNext pNode-m_pNext-m_pNext;}}if (pToBeDeleted ! NULL){delete pToBeDeleted;pToBeDeleted NULL;}
}
下面是这道算法题的题目 输入一个链表的头结点从尾到头反过来打印出每个结点的值。 这里假设不能修改链表的结构首先肯定是需要遍历整个链表遍历也是从头到尾的顺序但输出顺序却是从尾到头所以这里可以使用栈来进行辅助。因此实现代码如下
// 从尾到头打印链表迭代输出
void PrintListReversingly_Iteratively(ListNode* pHead){std::stackListNode* nodes;ListNode* pNode pHead;while (pNode ! NULL){nodes.push(pNode);pNode pNode-m_pNext;}while (!nodes.empty()){pNode nodes.top();coutpNode-m_nValue ;nodes.pop();}cout endl;
}
这里既然想到使用栈来实现函数而递归本质上就是一个栈结构所以自然想到可以用递归来实现。实现代码如下
// 递归版本
void PrintListReversingly_Recursively(ListNode* pHead){if (pHead ! NULL){if (pHead-m_pNext ! NULL){PrintListReversingly_Recursively(pHead-m_pNext);}cout pHead-m_nValue ;}
}
更完整的代码例子可以查看从尾到头打印链表。
