4.1哈希表简介

使用哈希表，时间复杂度被认为是常数级别O(N)

哈希表在使用层面上可以理解为一种集合结构
如果只有key，没有伴随数据value，可以使用HashSet结构(C++中叫UnOrderedSet / UnSortedSet)
如果既有key，又有伴随数据value，可以使用HashMap结构(C++中叫UnOrderedMap / UnSortedMap)
有无伴随数据，是HashMap和HashSet唯一的区别，底层的实际结构的一回事
使用哈希表增(put)、删(remove)、改(put)(更新的不是key是value)、查(get)的操作，可以认为时间复杂度为O(1)，但是常数时间比较大
放入哈希表的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小
放入哈希表的东西，如果不是基础类型，内部按引用传递，内存占用是这个东西内存地址的大小

(key如果是一个长字符串，哈希表在基础类型时，值传递，所以拷贝此长字符串，所以造成空间使用很多。哈希表在不是基础类型时，引用传递，所以拷贝此长字符串地址放在哈希表内)
（nodeA=new Node(1); nodeB=new Node(1);这两个在哈希表中不是一个东西，因为nodeA有自己的地址， nodeB也有自己的地址，虽然 nodeA和 nodeB值相同，但是哈希表根据地址做的划分）

4.2有序表简介

性能相对哈希表差一点，时间复杂度O(logN)

有序表在使用层面上可以理解为一种集合结构
如果只有key，没有伴随数据value，可以使用TreeSet结构(C++中叫OrderedSet)
如果既有key，又有伴随数据value，可以使用TreeSet结构(C++中叫OrderedMap)
有无伴随数据，是TressSer和TressMap唯一的区别，底层的实际结构的一回事
有序表和哈希表的区别是，有序表把key按照顺序组织起来，而哈希表完全不组织
红黑树、AVL树、size-balance-tree和跳表等都属于有序表结构，只是底层具体实现不同
放入有序表的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小
放入有序表的东西，如果不是基础类型，必须提供比较器(告诉编译器怎么排序)，内部按引用传递，内存占用是这个东西内存地址的大小
不管是什么底层具体实现，只要是有序表，都有以下固定的基本功能和固定的时间复杂度

有序表的固定操作：

1. void put(K key，V value): 将一个 (key，value) 记录加入到表中，或者将key的记录更新成value。
   2)V get(K key):根据给定的key，查询value并返回
2. void remove(K key):移除key的记录。
   4)boolean containsKey(K key):问是否有关于key的记录。
   5)K firstKey():返回所有键值的排序结果中，最左(最小)的那个。
   6)K lastKey():返回所有键值的排序结果中，最右(最大)的那个。
   7)K floorKey(K key):如果表中存入过key，返回key; 否则返回所有键值的排序结果中key的前一个。
   8)K ceilingKey(K key):如果表中存入过key，返回key;否则返回所有键值的排序结果中key的后一个。

4.3链表

单链表的节点结构

Class Node<v>
{V value;Node next;
}

由以上结构的节点依次连接起来所形成的链叫单链表结构

双链表的节点结构

Class Node<v>
{V value;Node next;Node last;
}

由以上结构的节点依次连接起来所形成的链叫双链表结构

单链表和双链表结构只需要给定一个头部节点head，就可以找到剩下的所有的节点

创建一个单向链表的过程

#include <iostream>
#include <string>using namespace std;struct Student {string name;int age;string major;Student* next;
};class StudentList {
private:Student* head;public:StudentList() {head = nullptr;}void addStudent(const string& name, int age, const string& major) {// 创建新的学生节点Student* newStudent = new Student;newStudent->name = name;newStudent->age = age;newStudent->major = major;newStudent->next = nullptr;//表示链表没有下一个节点// 如果链表为空，将新节点作为头节点if (head == nullptr) {head = newStudent;}else {// 找到链表最后一个节点，将新节点插入到链表末尾Student* current = head;while (current->next) {current = current->next;}current->next = newStudent;}}void displayStudents() {Student* current = head;if (current == nullptr) {cout << "学生列表为空." << endl;return;}while (current) {cout << "姓名: " << current->name << ", 年龄: " << current->age << ", 专业: " << current->major << endl;current = current->next;}}
};int main() {// 创建学生链表对象StudentList studentList;// 添加学生信息studentList.addStudent("小明", 18, "计算机科学");studentList.addStudent("小红", 19, "数学");studentList.addStudent("小李", 20, "物理");// 显示学生信息studentList.displayStudents();return 0;
}

创建一个双向链表的过程

#include <iostream>
#include <string>using namespace std;struct Student {string name;int age;string major;Student* prev; // 添加前驱指针Student* next; // 添加后继指针
};class StudentList {
private:Student* head;public:StudentList() {head = nullptr;}void addStudent(const string& name, int age, const string& major) {// 创建新的学生节点Student* newStudent = new Student;newStudent->name = name;newStudent->age = age;newStudent->major = major;newStudent->prev = nullptr;newStudent->next = nullptr;// 如果链表为空，将新节点作为头节点if (head == nullptr) {head = newStudent;}else {// 找到链表最后一个节点，将新节点插入到链表末尾Student* current = head;while (current->next) {current = current->next;}current->next = newStudent;newStudent->prev = current;}}void displayStudents() {Student* current = head;if (current == nullptr) {cout << "学生列表为空." << endl;return;}while (current) {cout << "姓名: " << current->name << ", 年龄: " << current->age << ", 专业: " << current->major << endl;current = current->next;}}};int main() {// 创建学生链表对象StudentList studentList;// 添加学生信息studentList.addStudent("小明", 18, "计算机科学");studentList.addStudent("小红", 19, "数学");studentList.addStudent("小李", 20, "物理");// 显示学生信息studentList.displayStudents();return 0;
}

4.3.1例1-反转单向和双向链表

【题目】分别实现反转单向链表和反转双向链表的函数
【要求】如果链表长度为N，时间复杂度要求为O(N),额外空间复杂度要求为O(1)

本身链表为1节点连2节点，2节点连3节点
反转操作为3节点连2节点，2节点连1节点

如果没有换头操作，可以定义为void类型。如果换头了，那就需要带有返回值（本身链表为1节点连2节点，2节点连3节点，123。反转操作为3节点连2节点，2节点连1节点，321.所以head=f（head），head指向3节点了）

在上述单向链表代码中StudentList类中加入，调用时即可反转单向链表

void ReverseList() {if (head == nullptr || head->next == nullptr) {return;}Student* prev = nullptr;Student* current = head;Student* next = nullptr;while (current != nullptr) {// 保存下一个节点的指针next = current->next;// 反转当前节点的指针current->next = prev;// 移动指针位置prev = current;current = next;}// 更新头节点指针head = prev;}

在上述双向链表代码中StudentList类中加入，调用时即可反转单向链表

void reverseList() {if (head == nullptr || head->next == nullptr) {// 空链表或只有一个节点，无需反转return;}Student* current = head;Student* prev = nullptr;while (current) {// 保存当前节点的下一个节点Student* next = current->next;// 反转当前节点的指针current->next = prev;current->prev = next;// 更新prev和current指针prev = current;current = next;}// 更新头节点head = prev;}

4.3.2例2-打印两个有序链表的公共部分

【题目】给定两个有序链表的头指针head1和head2，打印两个链表的公共部分
【要求】如果两个链表的长度之和为N，时间复杂度要求为O(N),额外空间复杂度要求为O(1)

链表1指针先指向1，链表2指针先指向0，
对比，谁小谁移动，链表2指针先指向2，
对比，谁小谁移动，链表1指针先指向2，
对比，相等，打印2，共同移动，链表1指针先指向5，链表2指针先指向3，
对比，谁小谁移动，链表2指针先指向5，
对比，相等，打印5，共同移动，越界，停止
打印出看2，5

此方法注意要升序排列

#include <iostream>
#include <string>using namespace std;struct Student {string name;int age;string major;Student* next;
};class StudentList {
private:Student* head;public:StudentList() {head = nullptr;}void addStudent(const string& name, int age, const string& major) {// 创建新的学生节点Student* newStudent = new Student;newStudent->name = name;newStudent->age = age;newStudent->major = major;newStudent->next = nullptr;//表示链表没有下一个节点// 如果链表为空，将新节点作为头节点if (head == nullptr) {head = newStudent;}else {// 找到链表最后一个节点，将新节点插入到链表末尾Student* current = head;while (current->next) {current = current->next;}current->next = newStudent;}}void displayStudents() {Student* current = head;if (current == nullptr) {cout << "学生列表为空." << endl;return;}while (current) {cout << "姓名: " << current->name << ", 年龄: " << current->age << ", 专业: " << current->major << endl;current = current->next;}}void printCommonPart(StudentList list2) {Student* p1 = head;Student* p2 = list2.head;cout << "两个链表的公共部分: ";while (p1 && p2) {if (p1->age < p2->age) {p1 = p1->next;}else if (p1->age > p2->age) {p2 = p2->next;}else{cout << p1->age << " ";p1 = p1->next;p2 = p2->next;}}cout << endl;}
};int main() {// 创建学生链表对象StudentList studentList1;// 添加学生信息studentList1.addStudent("小明", 10, "计算机科学");studentList1.addStudent("小红", 20, "数学");studentList1.addStudent("小李", 30, "物理");StudentList studentList2;// 添加学生信息studentList2.addStudent("小红", 20, "数学");studentList2.addStudent("大明", 40, "计算机科学");studentList2.addStudent("大李", 60, "物理");// 显示学生信息studentList1.displayStudents();studentList2.displayStudents();cout << "----------------------------------" << endl;studentList1.printCommonPart(studentList2);return 0;
}

4.3.3面试时链表解题的方法论

对于笔试，不用太在乎空间复杂度，一切为了时间复杂度
对于面试，时间复杂度依然放在第一位，但是一定要找到空间最省的方法

重要技巧：
额外数据结构记录（哈希表等）
快慢指针

4.3.4例3-判断一个链表是否为回文结构

【题目】给定一个单链表的头节点head，请判断该链表是否为回文结构（正念反念一样）
【例子】1->2->1，返回true；1->2->2->1，返回true；1->20->3->20->1，返回true；1->2->3，返回false
【条件】如果链表长度为N，时间复杂度达到O(N),额外空间复杂度达到O(1)

1->2->3->2->1
笔试：
依次把各个节点放到栈中，栈弹出的顺序是链表逆序的顺序，比对，有一步不一样即不是回文结构

#include<iostream>
#include <stack>
struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}
};bool isPalindrome(ListNode* head) {std::stack<ListNode*> stack;//创建一个空栈 stackListNode* cur = head;while (cur != nullptr) {//遍历整个链表，将每个节点指针都压栈，直到遍历到链表的尾节点stack.push(cur);cur = cur->next;}while (head != nullptr) {//再次遍历链表，同时从栈中弹出元素，依次与链表当前节点比较if (head->val != stack.top()->val) {return false;}stack.pop();head = head->next;}return true;
}
int main()
{// 创建一个示例链表: 1 -> 2 -> 3 -> 2 -> 1ListNode* node1 = new ListNode(1);ListNode* node2 = new ListNode(2);ListNode* node3 = new ListNode(3);ListNode* node4 = new ListNode(2);ListNode* node5 = new ListNode(1);node1->next = node2;node2->next = node3;node3->next = node4;node4->next = node5;// 调用判断函数bool result = isPalindrome(node1);// 输出结果if (result) {std::cout << "该链表是回文链表" << std::endl;}else {std::cout << "该链表不是回文链表" << std::endl;}// 释放内存delete node1;delete node2;delete node3;delete node4;delete node5;return 0;
}

省一点空间的做法：
把一半的右边的节点放到栈中，栈弹出的和正序进行比对，有一步不一样即不是回文结构
省了1/2的空间
怎么知道放完了一半的右边的节点，一个指针达不成要求，需要两个指针,一前一后

#include<iostream>
#include<vector>
int main()
{std::vector<int> arr= { 1,2,3,3,1,2,1 };int length = sizeof(arr) / sizeof(arr[0]);std::vector<int>::iterator Begin = arr.begin();std::vector<int>::iterator End = arr.end()-1;bool isPalindrome = true; while (Begin < End){if (*Begin != *End){isPalindrome = false;break; }Begin++;End--;}if (isPalindrome){std::cout << "true" << std::endl;}else{std::cout << "false" << std::endl;}return 0;
}

快慢指针做法：
快指针一次走两步，慢指针依次走一步，当快指针走到终点时，慢指针在中间
把一半的右边的节点放到栈中，栈弹出的和正序进行比对，有一步不一样即不是回文结构

#include<iostream>
#include <stack>
struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}
};bool isPalindrome(ListNode* head) {if (head == nullptr || head->next == nullptr) {return true;}ListNode* slow = head;ListNode* fast = head;//fast每次向后移动两个节点，直到fast达到链表的末尾或倒数第二个节点。while (fast->next != nullptr && fast->next->next != nullptr) {slow = slow->next;fast = fast->next->next;}//循环结束后，当快指针达到链表尾部或倒数第二个节点时循环结束，此时慢指针所指的节点即为链表的中间节点（针对奇数长度链表）或者右半部分链表的第一个节点（针对偶数长度链表）slow = slow->next;//将慢指针向后移动一个节点，执行右半部分链表的第一个节点std::stack<int> stack;//创建一个整型的栈//右半部分链表的节点依次入栈while (slow != nullptr) {stack.push(slow->val);slow = slow->next;}//比较ListNode* cur = head;while (!stack.empty() && cur != nullptr) {if (stack.top() != cur->val) {return false;}stack.pop();cur = cur->next;}return true;
}int main() {// 创建一个示例链表: 1 -> 2 -> 3 -> 2 -> 1ListNode* node1 = new ListNode(1);ListNode* node2 = new ListNode(2);ListNode* node3 = new ListNode(3);ListNode* node4 = new ListNode(2);ListNode* node5 = new ListNode(1);node1->next = node2;node2->next = node3;node3->next = node4;node4->next = node5;// 调用判断函数bool result = isPalindrome(node1);// 输出结果if (result) {std::cout << "该链表是回文链表" << std::endl;}else {std::cout << "该链表不是回文链表" << std::endl;}// 释放内存delete node1;delete node2;delete node3;delete node4;delete node5;return 0;
}

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:bool isPalindrome(ListNode* head) {if (head == nullptr || head->next == nullptr) {return true; // 空链表或只有一个节点的链表视为回文链表}ListNode* fast = head->next;ListNode* slow = head;// 快慢指针找到链表的中间节点while (fast != nullptr && fast->next != nullptr) {fast = fast->next->next;slow = slow->next;}// 反转后半部分链表ListNode* prev = nullptr;ListNode* curr = slow->next;while (curr != nullptr) {ListNode* nextNode = curr->next;curr->next = prev;prev = curr;curr = nextNode;}// 比较前半部分和反转后的后半部分链表ListNode* cur1 = head;ListNode* cur2 = prev;while (cur1 != nullptr && cur2 != nullptr) {if (cur1->val != cur2->val) {return false;}cur1 = cur1->next;cur2 = cur2->next;}return true;}
};

4.3.4.1快慢指针

如快指针一次走两步，慢指针依次走一步，当快指针走到终点时，慢指针在中间

需要熟练使用快慢指针
链表长度为1时，链表长度为2时，链表长度为3时，链表长度为小数时最特殊
情况1
1->2->3->2->1
奇数个时，当快指针走完，慢指针正好压中中间点，3
1->2->3->3->2->1
偶数个时，当快指针走完，慢指针正好压中中间点的前一个，3

情况2
1->2->3->2->1
奇数个时，当快指针走完，慢指针正好压中中间点，3
1->2->3->3->2->1
偶数个时，当快指针走完，慢指针正好压中中间点的后一个，3

情况3
1->2->3->2->1
奇数个时，当快指针走完，慢指针压中中间点前一个的位置，2
1->2->3->3->2->1
偶数个时，当快指针走完，慢指针压中中间点的前一个位置，2

4.3.5例4-将单向链表按某值划分成左边小、中间相等、右边大的形式

【题目】给定一个单链表的头节点head，节点的值类型是整型，再给定一个整数pivot。实现一个调整链表的函数，将链表调整为做部分都是值小于pivot的节点，中间部分都是值等于pivot的节点，右部分都是值大于pivot的节点
【进阶】在实现原问题功能的基础上增加如下要求
【要求】调整后所有小于pivot的节点之间的相对顺序和调整前一样
【要求】调整后所有等于pivot的节点之间的相对顺序和调整前一样
【要求】调整后所有小于pivot的节点之间的相对顺序和调整前一样
【要求】时间复杂度达到O(N),额外空间复杂度达到O(1)

笔试：
把单链表每一个节点放到数组中，选一个值做划分值，小于放左边，等于放中间，大于放右边，再重新串起来

面试：
数组中做不到相对顺序等，单链表可以做到
4->6->3->5->8->5->2->5->9
六个变量H头T尾，S小于，E等于，B大于
SH=NULL , ST=NULL , EH=NULL , ET=NULL , BH=NULL , BT=NULL

来到4节点,小于5
SH=4 , ST=4
来到6节点，大于5
BH=6 , BT=6
来到3节点,小于5, SH、ST不为空让ST指向3
SH=4 , ST=3
来到5节点,等于5
EH=5 , ET=5
来到8节点，大于5,BH、BT不为空让BT指向8
BH=6 , BT=8
来到5节点,等于5, ET不为空让ET指向5
EH=5 , ET=5
来到2节点,小于5, SH、ST不为空让ST指向2
SH=4 , ST=2
来到5节点,等于5, ET不为空让ET指向5
EH=5 , ET=5
来到9节点，大于5,BH、BT不为空让BT指向9
BH=6 , BT=9

连接

如果没有大于5的区域？如果没有等于5的区域？如果没有小于5的区域？
如果同时没有大于5的区域等于5的区域？
所以再三块重连时要讨论清楚连接
否则连上空指针会报错

4.3.6例5-复制好友随机指针节点的链表

【题目】一种特殊的单链表节点描述如下

class Node{int value;Node next;Node rand;Node(int val){value=val;}
}

rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节点，也可能指向NULL。给定一个由Node节点类型组成的无环单链表的头节点head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点
【要求】时间复杂度O(N),额外空间复杂度O(1)

【解析】这个链表上每个节点由next和rand两个指针，next继续链表连接，rand不一定指向哪里

目的复制出一个一样的链表

4.3.6.1方法1-利用哈希表

用额外空间时：
可以用哈希表map，key表示老节点，value表示克隆出来的新节点
遍历，(1,1’)放到map中，(2,2’)放到map中，(3,3’)放到map中
遍历哈希表或老链表均可，下述遍历老链表的方式
遍历到老链表1，查出新链表的1‘，通过老链表2和map查出新链表2’，让1‘next到2’，通过老链表3和map查出新链表3’，让1‘rand到3’
遍历到老链表2，查出新链表的2‘，通过老链表3和map查出新链表3’，让2‘next到3’，通过老链表1和map查出新链表1’，让2‘rand到1’
遍历到老链表3，查出新链表的3‘，通过老链表NULL和map知rand NULL，让3‘next到NULL，通过老链表3和map知rand NULL，让3‘rand到NULL

返回1‘即可

4.3.6.1方法2-不利用哈希表

生成克隆节点，放在老链表老节点后，先不看rand指针

通过1节点rand找到3节点，因为克隆节点放在老链表老节点后，所以可以用3节点next找到3’节点，所以1‘rand3’

如此操作得出

之后在next方向上把新老链表分离即可

4.3.7例6-两个单链表相交的一系列问题

【题目】给定两个可能有环也可能无环的单链表，头节点head1和head2.请实现一个函数，如果两个链表相交，请返回相交的第一个节点。如果不相交，返回NULL
【要求】如果两个链表长度之和为N，时间复杂度达到O(N)，额外空间复杂度到大O(1)

4.3.7.1判断环方法1哈希表

遍历一个就放入容器一个，如果是环，当count发现重复就是环，不重复就不是环，发现的这个节点即是第一个入环节点

4.3.7.2判断环方法2快慢指针

慢指针一次走一个，快指针一次走两个，如果没有环，快指针会走到空就知道了没有环，如果有环就会一直走，总会碰上
快指针和慢指针碰上后，快指针回到头，快慢指针都一次走一步，它们一定会在第一个入环节点相遇

4.3.7.3情况1都无环

左边情况必定不存在，因为这样会有一个节点有两个next了，错误
遍历第一个链表，记录头head1，尾end1，长度len1
第二个链表，记录头head2，尾end2，长度len2
先判断end1和end2内存地址是不是一个，（因为无环时必定只有上图右边情况，如果相交，最后一个节点必定两个链表共有）
如果不是，必定不相交
如果是，知head1和head2的长度，先从长的走到和短的一样的剩余长度，开始一起遍历对比，一定会共同到达第一个交点


n为链表1长度减去链表2长度的值

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if(headA==nullptr||headB==nullptr){return nullptr;}ListNode*PA=headA;ListNode*PB=headB;int num=0;while(PA->next!=nullptr){num++;PA=PA->next;}while(PB->next!=nullptr){num--;PB=PB->next;}if(PA!=PB){return nullptr;}PA=num>0?headA:headB;PB=PA==headA?headB:headA;num=abs(num);while(num!=0){num--;PA=PA->next;}while(PA!=PB){PA=PA->next;PB=PB->next;}return PA;}
};

std::abs是取绝对值

4.3.7.4情况2两个链表其中一个有环，不可能相交

没有这种情况

4.3.7.5情况3两个链表都有环

有三种情况

因为已经算出了head1和head2的入环的第一个节点loop1和loop2
所以loop1=loop2的话是第二种情况
第二种情况可以算出两个链表从头到loop1的长度
和之前无环情况1相同，让长的到达节点使两个和长度相桶，之后同时开始遍历

之后开始区分情况1和情况3，从loop1开始往下走，loop2不动，在转回到loop1之前如果能碰到loop2就是情况3，碰不到就是情况1

汇总