1. 单链表删除节点的方式总结
- 复杂度O(n)， 后继结点的值覆盖掉要删除元素的值，最后再将重复元素断链即达到了删除重复结点的方法。（前提是必须为中间节点）
- 复杂度O(1) ，已知头节点的情况下，遍历扫描到前一个节点，将其next指针指向删除节点的下一个节点。
2. 有序/无序链表 删除重复元素
- 有序情况下：依次遍历列表，比较当前节点和下一个节点值，如果节点值相同， 直接将当前节点指向下下一个节点，即变为删除节点的问题。
- 无序情况下： 可用哈希表对节点值进行存储和查找，如果第i个节点值已经存在，则将第i-1个节点的指针指向i+1个节点，完成第i个节点的删除操作。
两个方法都需要注意尾节点的特殊处理！
3. 删除链表中等于给定值 val 的所有节点。
- 迭代法O(N)： 遍历链表依次删除符合条件的节点，注意头节点的特殊情况
最后返回值 return head->val==val?head->next:head;
- 递归法O(N): 递归调用函数，依次遍历链表删除节点，递归结束条件即为节点为空时，返回NULL。
递归语句 head->next = removeElements(head->next, val);
- 增加梢兵节点: 避免头节点以及删除后链表为空的情况。即在链表头部增加一个新节点，节点next指针指向原链表的head。
ListNode* first = new ListNode(0); 增加一个值为0的梢兵节点
first->next = head;
4. 回文链表判断
- 时间复杂度O(N) 空间复杂度也为O(N): 先将链表元素遍历一遍存储到数组vector中，然后利用两个指针分别从数组两端进行判断，只要两者值不相同即返回false，否则一直向中间靠拢判断，直到两者相遇结束。
vector<int> res;
if(res[i] != res[res.size()-1-i]) return false;
- 时间复杂度为O(N) 空间复杂度为O(1): 从链表的中间开始，先对链表后半部分进行反转，然后采用两个指针，分别从链表两端开始比较节点值，不想等则立即返回false，相等则继续比较下一个节点直到其中一个链表遍历结束。（考虑链表长度为奇数或偶数）
- 优化做法：可在第一次遍历链表寻找中间点的过程中，同时反转前半部分链表。然后直接两个指针从中间向两端依次比较节点值是否相同。
5. 有序链表转换二叉搜索树
链表转数组, 然后递归查找中间元素作为根节点。优点数组查找时间复杂度相比较链表而言为O(1)。整个算法、空间时间复杂度都为O(N)。
直接遍历链表, 找到中间节点即为根节点, 然后递归分别遍历左右两部分。时间复杂度为O(NlogN)
6. 两两交换链表相邻的节点
增加梢兵节点：当链表节点数不小于1个时，链表的头节点会发生变化。因此可以增加一个梢兵节点做为新的头节点，next指针指向原来的头节点head。然后运用指针进行节点交换操作，注意指针步长为2步。
不增加梢兵节点： 可以将head->next事先作为新的头节点，再按上面方面对原链表进行交换操作，最终返回新头节点即可。
递归方法解决：将上述方法化解为对子单元对递归处理
if(head == NULL || head->next == NULL) return head;
ListNode* Next = head->next;
head->next = swapPairs(Next->next);
Next->next = head;
return Next;
7. Map<type1, type2>中的元素查找
- A.count(element)，是返回被查找元素的个数。因为map不存在相同元素，所以返回值为0或1
- A.find(element)，是返回被查找元素的位置，没有则返回map.end()
