每日算法题：Day 28（数据结构）
每日算法题：Day 28（数据结构）
作者：TeddyZhang，公众号：算法工程师之路
Day 28, 数据结构知识点走起~
1
编程题
【剑指Offer】删除链表中重复的节点
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
思路： 首先题目说了这是一个排序链表，因此所有重复的数一定会是在一起的，这样我们改变指针的指向，就可以将这些重复的一次性去除完，在遍历的时候，如果相邻两个数重复，我们要进入一个循环进行判断，由于需要这些重复数的边界，因此我们需要使用pre和last指针用来得到其边界，然后进行删除！
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead)
{
ListNode* dummy = new ListNode();
dummy->next = pHead; // 设置哨兵节点，以防止头节点被删除的情况
ListNode* pre = dummy;
ListNode* last = dummy->next;
while(last != nullptr){
if(last->next != nullptr && last->val == last->next->val){
// 如果两个相邻节点重复，那么需要循环判断
while(last->next != nullptr && last->val == last->next->val){
last = last->next;
}
pre->next = last->next;
last = last->next;
}else{
pre = pre->next;
last = last->next;
}
}
return dummy->next;
}
};
【剑指Offer】二叉树的下一节点
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
思路： 这道题目很坑人的就是parent指针不叫parent，叫做next, 也太奇葩了吧，不过无所谓啦，中序遍历的下一个节点主要分为两种情况：
- 情况一: 该节点存在右子树，则右子树的最左端的节点即为该节点的下一节点，我们遍历去寻找就可以了！
- 情况二: 该节点不存在右子树，则可以分成两种情况： 1.如果该节点为右节点，那么需要一直向上遍历，直到找到某个节点是左节点，停止，则左节点的父节点为下一节点。 2.如果该节点为左节点，那么其父节点为下一节点！
/*
struct TreeLinkNode {
int val;
struct TreeLinkNode *left;
struct TreeLinkNode *right;
struct TreeLinkNode *next;
TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
}
};
*/
class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
if(pNode == nullptr)
return nullptr;
TreeLinkNode* pNext = nullptr;
if(pNode->right != nullptr) //情况一：有右子树
{
TreeLinkNode* pRight = pNode->right;
while(pRight->left != nullptr)
pRight = pRight->left; //查找右子树的最左端节点
pNext = pRight;
}
else if(pNode->next != nullptr) //情况二：右子树为空
{
TreeLinkNode *pCurrent = pNode;
TreeLinkNode *pParent = pNode->next;
while(pParent != nullptr && pCurrent == pParent->right)
//2.1 右子树为空且该节点为右节点，则一直向上查找，直到该节点为父节点的左节点，
//则该节点的父节点为下一节点
{
pCurrent = pParent;
pParent = pParent->next;
}
//2.2 右子树为空且为左节点，则父节点为下一节点
pNext = pParent;
}
return pNext;
}
};2
概念题
【数据结构】解决哈希冲突的方法，开放地址法和拉链法的区别
开放地址法：当地址发生冲突时，按照某种方法（线性探测法）去继续探测其他储存单元，直到有空位置位置！注意：开放地址法删除元素不可以直接删除，这样会截断其他具有相同哈希值元素的查找地址，因此通常使用标志位标记该元素已被删除！
拉链法：如果出现了哈希冲突，则在冲突位置建立一个新链表，并将冲突的元素依次添加到链表后，这样会避免空间的浪费！
区别以及优缺点：
- 拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
- 由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
- 开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
注意：装填因此α = 填入表中的元素 / 哈希表的长度
【数据结构】设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列那种存储方式最节省运算时间
插入操作中，单向链表循环链表要快于双向循环链表，只需要就该两个指针即可！但对于删除操作，怎么才能快速的找到尾结点是非常关键的问题，对于双向循环链表，其寻找尾结点的速度最快，直接找头结点的前驱节点即可！
但对于单向循环链表来说，却需要遍历整个链表！
【数据结构】哈夫曼树的一些节点性质
由于m叉哈夫曼树只有度为m和度为0的节点，因此如果是一棵二叉哈夫曼树，则节点总数为n2+n0.又因为对于一棵树来说 n0 = n2 + 1， 因此如果某一棵二叉哈夫曼树有N个叶子节点，那么总结点数为2N-1. 叶子节点也就是度为零的节点！