二叉树相关算法
链表相关知识点：
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
知识点一：链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
知识点二：相比于线性表顺序结构（数组），操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
知识点三：使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。
知识点四：链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。
链表有很多种不同的类型：单向链表，双向链表以及循环链表。
题目
合并两个排序的链表
典型题例：
输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。
示例 ：
输入：1->3->5 , 2->4->5 输出：1->2->3->4->5->5
思路
（二路归并)O(n)
- 新建头部的保护结点dummy，设置cur指针指向dummy。
- 若当前l1指针指向的结点的值val比l2指针指向的结点的值val小，则令cur的next指针指向l1，且l1后移；否则指向l2，且l2后移。
- 然后cur指针按照上一部设置好的位置后移。
- 循环以上步骤直到l1或l2为空。
- 将剩余的l1或l2接到cur指针后边。
时间复杂度
两个链表各遍历一次，所以时间复杂度为O(n)
代码：
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* merge(ListNode* l1, ListNode* l2) { //新建头部的保护结点 auto dummy = new ListNode(-1); auto cur = dummy; //新链表 //比较l1与l2对应位置的大小 while (l1 && l2){ if (l1->val <= l2->val){ cur->next = l1; //尾插新节点 cur = l1; //将当前的节点后移 l1 = l1->next; //l1 指针后移 } else{ cur->next = l2; cur = l2; l2 = l2->next; } } //判断哪个链表是还未插完，直接尾插入新链表 if (l1) cur->next = l1; else cur->next = l2; return dummy->next; //返回新链表的头节点 } };
复杂链表的复刻
典型题例：
实现一个函数可以复制一个复杂链表。
在复杂链表中，每个结点除了有一个指针指向下一个结点外，还有一个额外的指针指向链表中的任意结点或者null。
数据范围 ：
链表长度 [0,500]。
思路
核心：
使用hash存储 key = 源链表节点，value = 目标链表节点，遍历源链表，判断每个节点和random节点是否在hash表中，如果不存在则创建
代码：
class Solution { public: ListNode *copyRandomList(ListNode *head) { unordered_map<ListNode*, ListNode*> hash; hash[nullptr] = nullptr; auto dup = new ListNode(-1), tail = dup; while(head) { if(!hash.count(head)) hash[head] = new ListNode(head->val); if(!hash.count(head->random)) hash[head->random] = new ListNode(head->random->val); tail->next = hash[head]; tail->next->random = hash[head->random]; tail = tail->next; head = head->next; } return dup->next; } };
充电站
推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习
