Q. 有序表和无序表（Hash表）区别？Key有无序的区别。
Q. map 和 set 区别：有无伴随数据的区别。
有序表：红黑树、AVL树、size-banlance-tree、跳表都是有序表
哈希表：基础类型，值传递；非基础类，必须提供比较器，引用传递。
【经典题目】反转链表。要求实现单链表、双链表结构，迭代和递归两种方式。
1 //迭代 2 ListNode* ReverseList(ListNode* head) 3 { 4 ListNode* prev = nullptr; 5 ListNode* curr = head; 6 while (curr) 7 { 8 ListNode* next = curr->next; 9 curr->next = prev; 10 prev = curr; 11 curr = next; 12 } 13 return prev; 14 }
1 //递归 2 ListNode* ReverseList(ListNode* head) 3 { 4 if (!head || !head->next) 5 return head; 6 7 ListNode* newHead = ReverseList(head->next); 8 head->next->next = head; 9 head->next = nullptr; 10 11 return newHead; 12 }
快慢指针
两个指针p1，p2，p1每次+1，p2每次+2，直到越界前。
Q. 用链表做荷兰国旗问题
思路：准备6个指针，SH指向小于num的头，ST指向小于num的尾；EH指向等于num的头结点，ET指向等于num的尾结点；MH指向大于num的头结点，MT指向大于num的尾结点。
Q. 复制含有随机指针节点的链表
1 class Node{ 2 int value; 3 Node next; 4 Node rand; 5 Node(int val){ 6 value = val; 7 } 8 }