哈希表：使用时，认为时间复杂度是常数级别，但常数时间比较大
- unordered_map
- unordered_set
-
哈希表在使用层面上可以理解为一种集合结构
-
如果只有key，没有伴随数据value，可以使用HashSet结构（C++中叫unordered_set）
-
如果既有key，又有伴随数据value，可以使用HashMap结构（C++中叫unordered_map）
-
有无伴随数据，是HashMap和HashSet唯一的区别，底层的实际结构是一回事
-
使用哈希表增(put_、删(remove)、改(put)和查(get)的操作，可以认为时间复杂度为O(1)，但是常数时间比较大
-
放入哈希表的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小
-
放入哈希表的东西，如果不是基础类型，内部按引用传递，内存占用是这个东西内存地址的大小
有序表：
- map
- set
-
有序表在使用层面上可以理解为一种集合结构
-
如果只有key，没有伴随数据value，可以使用TreeSet结构（C++中叫set）
-
如果既有key，又有伴随数据value，可以使用TreeMap结构（C++中叫map）
-
有无伴随数据，是TreeSet和TreeMap唯一的区别，底层的实际结构是一回事
-
有序表和哈希表的区别是，有序表把key按照顺序组织起来，而哈希表完全不组织
-
红黑树、AVL树、size—balance—tree和跳表等都属于有序表结构，只是底层具体实现不同
-
放入有序表的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小
-
放入有序表的东西，如果不是基础类型，必须提供比较器，内部按引用传递，内存占用是这个东西内存地址的大小
-
不管是什么底层具体实现，只要是有序表，都有以下固定的基本功能和固定的时间复杂度
单链表的节点结构
// 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) {}
};双链表的节点结构
struct ListNode {
int val;
ListNode *next;
ListNode *last;
ListNode() : val(0), next(nullptr), last(nullptr) {}
ListNode(int x) : val(x), next(nullptr), last(nullptr) {}
ListNode(int x, ListNode *next, ListNode* last) : val(x), next(next), last(last) {}
};单链表和双链表结构只需要给定一个头部节点head，就可以找到剩下的所有节点。
[题目]：分别实现反转单向链表和反转双向链表的函数
[要求]：如果链表的长度为N，时间复杂度要求为O(N)，额外空间复杂度要求为O(1)
- 反转单向链表
- leetcode: 206. 反转链表
✅tested
ListNode* reverseList(ListNode* head) {
ListNode* pre = nullptr;
ListNode* cur = head;
while(cur){
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}- 反转双向链表
ListNode* reverseList(ListNode* head) {
ListNode* pre = NULL;
ListNode* cur = head;
while(cur){
ListNode* next = curr->next;
cur->next = prev;
cur->last = next;
pre = cur;
cur = next;
}
return pre;
}[题目]：给定两个有序链表的头指针head1和head2，打印两个链表的公共部分
[要求]：如果链表的长度为N，时间复杂度要求为O(N)，额外空间复杂度要求为O(1)
- leetcode: 剑指 Offer 25. 合并两个排序的链表 ✅tested
void printPublicList(ListNode* head1, ListNode* head2) {
ListNode* p1 = head1;
ListNode* p2 = head2;
while (p1 != nullptr && p2 != nullptr) {
if (p1->value == p2->value) {
cout << p1->value << endl;
p1 = p1->next;
p2 = p2->next;
}
else if (p1->value < p2->value) {
p1 = p1->next;
}
else {
p2 = p2->next;
}
}
}- 对于笔试，不用太在乎空间复杂度，一切为了时间复杂度
- 对于面试，时间复杂度依然放在第一位，但是一定要找到空间最省的方法
重要技巧：
- 额外数据结构记录（哈希表等）
- 快慢指针
[题目] 给定一个单链表的头节点head，请判断该链表是否为回文结构。
[例子] 1->2->1，返回true；1->2->2->1，返回true；15->6->15，返回true；1->2->3，返回false。
[要求] 如果链表长度为N，时间复杂度达到O(N)，额外空间复杂度达到O(1)。
（笔试）方法一：全部压到栈中。额外空间复杂度O(N)
bool isPalindrome1(ListNode* head) {
stack<ListNode*> s;
ListNode* cur = head;
while (cur != nullptr) {
s.push(cur);
cur = cur->next;
}
while (head != nullptr) {
if (head->value != s.top()->value) {
return false;
}
s.pop();
head = head->next;
}
return true;
}（笔试）方法二：只把右侧压到栈中。额外空间复杂度O(N/2)
- 快慢指针
✅tested
bool isPalindrome2(ListNode* head) {
if(head == nullptr || head->next == nullptr){
return true;
}
ListNode* fast = head->next;
ListNode* slow = head;
while(fast->next && fast->next->next){
slow = slow->next;
fast = fast->next->next;
}
stack<ListNode*> s;
while(slow != nullptr){
s.push(slow);
slow = slow->next;
}
while(!s.empty()){
if(head->val != s.top()->val){
return false;
}
s.pop();
head = head->next;
}
return true;
}（面试）方法三：额外空间复杂度O(1)
✅tested
bool isPalindrome3(ListNode* head) {
if(head == nullptr || head->next == nullptr){
return true;
}
// 找到前半部分链表的尾节点并反转后半部分链表
ListNode* firstHalfEnd = endOfFirstHalf(head);
ListNode* secondHalfStart = reverseList(firstHalfEnd->next);
// 判断是否回文
ListNode* p1 = head;
ListNode* p2 = secondHalfStart;
bool result = true;
while(p2 != nullptr){
if(p1->val != p2->val){
result = false;
break;
}
p1 = p1->next;
p2 = p2->next;
}
// 还原链表并返回结果
firstHalfEnd->next = reverseList(secondHalfStart);
return result;
}
ListNode* reverseList(ListNode* head) {
ListNode* pre = nullptr;
ListNode* cur = head;
while(cur){
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
ListNode* endOfFirstHalf(ListNode* head){
ListNode* fast = head;
ListNode* slow = head;
while(fast->next && fast->next->next){
slow = slow->next; // slow -> mid
fast = fast->next->next;// fast -> end
}
return slow;
}[题目]：给定一个单链表的头节点head，节点的值类型是整型，再给定一个整数pivot。实现一个调整链表的函数，将链表调整为左部分都是值小于pivot的节点，中间部分都是值等于pivot的节点，右部分都是值大于pivot的节点。
[进阶]：在实现原问题功能的基础上增加如下的要求
[要求]：调整后所有小于pivot的节点之间的相对顺序和调整前一样
[要求]：调整后所有等于pivot的节点之间的相对顺序和调整前一样
[要求]：调整后所有大于pivot的节点之间的相对顺序和调整前一样
[要求]：时间复杂度请达到O(N)，额外空间复杂度请达到O(1)
- leetcode: 86. 分隔链表 ✅tested
笔试：
申请一个Node类型的数组，在数组上进行partitation面试：
ListNode* listPartition2(ListNode* head, int pivot){
ListNode* sH = nullptr;
ListNode* sT = nullptr;
ListNode* eH = nullptr;
ListNode* eT = nullptr;
ListNode* bH = nullptr;
ListNode* bT = nullptr;
ListNode* next = nullptr;
while (head != nullptr){
next = head->next;
head->next = nullptr;
if (head->value < pivot) {
if (sH == nullptr) {
sH = head;
sT = head;
}
else {
sT->next = head; //将旧的尾巴的next连向当前节点
sT = head; //将当前节点变成新的尾巴
}
}
else if (head->value == pivot) {
if (eH == nullptr) {
eH = head;
eT = head;
}
else {
eT->next = head;
eT = head;
}
}
else {
if (bH == nullptr) {
bH = head;
bT = head;
}
else {
bT->next = head;
bT = head;
}
}
head = next;
}
// small and equal reconnect
if (sT != nullptr) { //如果有小于区域
sT->next = eH;
eT = (eT == nullptr ? sT : eT);
}
// all reconnect
if (eT != nullptr) {
eT->next = bH;
}
return sH != nullptr ? sH : (eH != nullptr ? eH : bH);
} [题目]：一种特殊的单链表节点类描述如下
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};rand指针是单链表节点结构中新增的指针， rand可能指向链表中的任意一个节点，也可能指向null。给定一个由Node节点类型组成的无环单链表的头节点head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。
[要求]：时间复杂度O(N)，额外空间复杂度O(1)
（笔试）使用哈希表，额外空间复杂度：O(N)
✅tested
Node* copyRandomList(Node* head) {
if(head == NULL){
return NULL;
}
Node* cur = head;
unordered_map<Node*, Node*> map;
while(cur != NULL){
//map.insert(pair<Node*, Node*>(cur, new Node(cur->val)));
map[cur] = new Node(cur->val);
cur = cur->next;
}
cur = head;
while(cur != NULL){
map[cur]->next = map[cur->next];
map[cur]->random = map[cur->random];
cur = cur->next;
}
return map[head];
}（面试）额外空间复杂度：O(1)
✅tested
Node* copyRandomList(Node* head) {
if(head == NULL){
return NULL;
}
Node* cur = head;
Node* next = NULL;
// 1. 复制各节点，并构建拼接链表
while(cur != NULL){
next = cur->next;
cur->next = new Node(cur->val);
cur->next->next = next;
cur = next;
}
cur = head;
Node* copyNode = NULL;
// 2. 构建各新节点的 random 指向
while(cur != NULL){
next = cur->next->next;
copyNode = cur->next;
copyNode->random = cur->random != NULL ? cur->random->next : NULL;
cur = next;
}
Node* res = head->next;
cur = head;
// 3. 拆分两个链表
while(cur != NULL){
next = cur->next->next;
copyNode = cur->next;
copyNode->next = (next != NULL ? next->next : NULL);
cur->next = next;
cur = next;
}
return res;
}[题目]：给定两个可能有环也可能无环的单链表，头节点head1和head2。请实现一个函数，如果两个链表相交，请返回相交的第一个节点。如果不相交，返回null
[要求]：如果两个链表长度之和为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)
-
leetcode: 面试题 02.07. 链表相交 ✅tested
// 找到链表第一个入环节点，如果无环，返回null
ListNode* getLoopNode(ListNode* head) {
if (head == nullptr || head->next == nullptr || head->next->next == nullptr) {
return nullptr;
}
ListNode* n1 = head->next; // n1 -> slow
ListNode* n2 = head->next->next; // n2 -> fast
while (n1 != n2){
if (n2->next == nullptr || n2->next->next == nullptr) {
return nullptr;
}
n2 = n2->next->next;
n1 = n1->next;
}
n2 = head;
while (n1 != n2){
n1 = n1->next;
n2 = n2->next;
}
return n1;
}
// 如果两个链表都无环，返回第一个相交节点，如果不相交，返回null
ListNode* noLoop(ListNode* head1, ListNode* head2) {
if (head1 == nullptr || head2 == nullptr) {
return nullptr;
}
ListNode* cur1 = head1;
ListNode* cur2 = head2;
int n = 0;
while (cur1->next != nullptr){
n++;
cur1 = cur1->next;
}
while (cur2->next != nullptr) {
n--;
cur2 = cur2->next;
}
if (cur1 != cur2) {
return nullptr;
}
cur1 = n > 0 ? head1 : head2;
cur2 = (cur1 == head1 ? head2 : head1);
n = abs(n);
while (n != 0){
n--;
cur1 = cur1->next;
}
while (cur1 != cur2){
cur1 = cur1->next;
cur2 = cur2->next;
}
return cur1;
}
// 两个有环链表，返回第一个相交节点，不相交返回null
ListNode* bothLoop(ListNode* head1, ListNode* loop1, ListNode* head2, ListNode* loop2) {
ListNode* cur1 = nullptr;
ListNode* cur2 = nullptr;
if (loop1 == loop2) {
cur1 = head1;
cur2 = head2;
int n = 0;
while (cur1 != loop1){
n++;
cur1 = cur1->next;
}
while (cur2 != loop2) {
n--;
cur2 = cur2->next;
}
cur1 = n > 0 ? head1 : head2;
cur2 = (cur1 == head1 ? head2 : head1);
n = abs(n);
while (n != 0) {
n--;
cur1 = cur1->next;
}
while (cur1 != cur2){
cur1 = cur1->next;
cur2 = cur2->next;
}
return cur1;
}
else {
cur1 = loop1->next;
while (cur1 != loop1) {
if (cur1 == loop2) {
return loop1;
}
cur1 = cur1->next;
}
}
return nullptr;
}
ListNode* getIntersectNode(ListNode* head1, ListNode* head2) {
if (head1 == nullptr || head2 == nullptr) {
return nullptr;
}
ListNode* loop1 = getLoopNode(head1);
ListNode* loop2 = getLoopNode(head2);
if (loop1 == nullptr && loop2 == nullptr) {
return noLoop(head1, head2);
}
if (loop1 != nullptr && loop2 == nullptr) {
return bothLoop(head1, loop1, head2, loop2);
}
return nullptr;
}