4. 链表

Tags: 链表

排序算法稳定性

排序的稳定性：数组中值相同的个体之间，如果不因为排序而改变相对次序，就说这个排序是有稳定性的（同值保序）；否则就没有。

• 不具备稳定性的排序：选择排序、快速排序、堆排序
• 具备稳定性的排序：冒泡排序、插入排序、归并排序、一切桶排序思想下的排序
  • 冒泡排序和插入排序：在相等的时候就不要交换了
  • 归并排序：merge时，在左右两边相等的时候要优先拷贝左边的数字

排序的稳定性往往会用在对两个字段的排序中，比如说先根据字段1排序，然后再根据字段2排序。一般这种情况下都需要使用具有稳定性的排序。

排序总结

• 一般来说都会选择快速排序，实验证明快排的常数项时间是最少的。堆排是在空间复杂度要求很高的情况下使用的；而归并排序是在要求稳定性的时候使用的
• 基于比较的排序，能不能做到时间复杂度在$O(NlogN)$以下？：目前没有
• 基于比较的排序，在$O(NlogN)$的时间复杂度时，能不能保证在空间复杂度在$O(logN)$以下，同时还保证稳定性？：目前没有

常见的坑

1. 归并排序的额外空间复杂度可以变成$O(1)$，不要求掌握，非常难，可以参考归并排序 内部缓存法，但是会丢失稳定性，那就不如用堆排了
2. “原地归并排序”的帖子都是垃圾，让空间复杂度变成$O(1)$，会让归并排序的时间复杂度变成$O(N^2)$ → 不如用插入
3. 快速排序可以做到稳定性，但是空间复杂度会变成$O(N)$，可以参考论文01 stable sort，不如用归并

• 一个很傻逼的题，遇到就说不会，让面试官教你。
  • 题目：有一道题目，是奇数的放在数组左边，偶数放在数组右边，还要求原始的相对次序不变，时间复杂度$O(N)$，额外空间复杂度$O(1)$。
  • 这就是快排的那种01 stable sort的问题，坑3。

工程上对排序的改进

1. 充分利用综合排序（利用各自排序的优势来做拼装）
2. 稳定性的考虑

哈希表

1. 哈希表在使用层面上可以理解为一种集合结构
2. 如果只有key，没有伴随数据value，可以使用HashSet结构（c++中叫做UnOrderedSet）
3. 如果既有key，又有伴随数据value，可以使用HashMap结构（c++中叫做UnOrderedMap）
4. 有无伴随数据，是HashMap和HashSet的唯一区别，底层的实际结构是一回事
5. 使用哈希表增（put）、删（remove）、改（put）和查（get）的操作，可以认为时间复杂度为$O(1)$，但是时间常数比较大
6. 放入哈希表的东西，如果是基础类型，内部按值传递(就是直接复制这个值)，内存占用就是这个东西的大小
7. 放入哈希表的东西，如果不是基础类型，内部按引用传递(即记录内存地址而不是值，是8字节)，内存占用是这个东西内存地址的大小

有序表

1. 有序表在使用层面上可以理解为一种数据结构
2. 如果只有key，没有伴随数据value，可以使用TreeSet结构（c++中叫做OrderedSet）
3. 如果既有key，又有伴随数据value，可以使用TreeMap结构（c++中叫做OrderedMap）
4. 有无伴随数据，是TreeMap和TreeSet的唯一区别，底层的实际结构是一回事
5. 有序表和哈希表的区别是：有序表把key按照顺序组织起来，整体式有序的，而哈希表则完全不组织，即无序组织key。因此哈希表能实现的东西有序表全能实现。
6. 由于其key的组织是有序的，因此有序表可以增加更多的API，比如找到最小的key，最大的key，离某个key最近的key
7. 红黑树、AVL树、size-balance-tree和跳表等都数据有序表结构，只是底层的具体实现不同
8. 放入有序表的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小
9. 放入有序表的东西，如果不是基础类型，内部按引用传递，内存占用是这个东西内存地址的大小（并且必须提供比较器，因为这是有序的，你不提供比较器，有序表不知道怎么组织）
10. 有序表的所有操作的时间复杂度都是$O(logN)$，$N$为有序表含有的记录数

单链表和双链表

• 单链表节点结构

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

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

• 双链表的节点结构

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

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

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

相关题目

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

重要技巧 a) 额外数据结构记录（栈、哈希表等） b) 快慢指针

1. 反转单向链表和双向链表，要求：若链表长度为N，时间复杂度要求为$O(N)$，空间复杂度为$O(1)$ [Leetcode 206]
2. 打印两个有序链表的公共部分 题目：给定两个有序链表的头指针head1和head2，打印两个链表的公共部分 要求：如果两个链表的长度之和为N，时间复杂度要求为$O(N)$，额外空间复杂度要求为$O(1)$ 思路：跟merge外排有有点像
3. 判断一个链表是否是回文结构 题目：给定一个单链表的haed，判断该链表是不是回文结构。比如1-2-3-2-1, 1-3-3-4-4-3-3-1都是回文结构 思路：
   1. 用栈来做，全部装进去之后再一个一个弹出来，跟链表从头比较，空间复杂度O(N)
   2. 同样用栈，但是只保存后半部分，然后弹出和链表的前半部分比较，比上一个少一半的空间O(N/2)，这需要使用快慢指针¹
   3. 通过改链表的方式来进行：同样使用快慢指针，快指针走完后慢指针指向中点，后慢指针继续走，并将后半部分的链表逆序，中点指向Null，逆序好后，从两边往中间走（一直走到Null，就是刚刚转成null的中点），一一对比，完全一样则回文，反之False。最后再将右边的链表逆序回来。这个额外空间为$O(1)$ 视频代码
4. 将单链表按照某值变成左边小中间等右边大的形式 思路：
   1. （笔试做法）把单链表每一个节点放到数组里去，然后在数组里完成这个任务，做完后在放到节点中。
   2. （面试做法）准备6个变量，分别是小于、等于、大于的头尾指针然后逐个遍历单链表（相当于构建了3个新的链表）最后再把这三个链表头尾串起来。但是最后需要考虑，万一某一个链表是空怎么办
5. 复制含有随机指针节点的链表
   • 即相当于单链表中的每个节点多出来一个随机指针指向其他的节点，或者null
   • 思路和题解
     • 哈希表，最简单
     • （面试思路）先遍历单链表，然后在每个节点后插入一个新的节点x'，此时只考虑正常的指针；接下来一对一对的看，把random指针给对应x'；最后把两者分离。
6. 如何判断链表有环？
   • 题目：如何判断链表有环？并返回第一个入环节点²
   • 备注：如果一个链表有环，那它一定不会有尾，因为有环的链表无法从环里走出来；如果走出来的话肯定需要有一个节点有两个next，这是不可能的。
   • 思路1：哈希表，遍历节点，并把节点（不是节点的值）逐一放进哈希表，当查到当前节点已经在哈希表里的时候，证明该点为第一个入环节点。（但是似乎额外空间复杂度有点大）
   • 思路2：快慢指针（不用额外数据结构），原因在于有环的单链表里快指针一定不会走到null（走到null就说明没环），而会和慢指针最终在环里相遇，而且在环中转的圈数不会超过两圈以上（快指针走两步，慢指针走一步）；两者相遇后，将快指针放到节点开头，慢指针不动，两者同时一步一步走，两者再相遇的时候一定是在第一个入环的节点（别管为啥，记住，不好证），此方法额外空间复杂度为$O(1)$
   • 题解：
7. 两个单链表相交的一系列问题（链接）
   • 题目：给定两个可能有环也可能无环的单链表，头节点head1和head2。请实现一个函数，如果两个链表相交³，则返回相交的第一个节点，如不相交，返回null。（要求：如果两个链表之和为$N$，请保证时间复杂度$O(N)$，额外空间复杂度$O(1)$）
   • 思路1：不考虑要求，可以使用两个哈希表实现，然后内部比较有无环，互相比较相不相交。
   • 思路2：（不采用哈希表的方法，需要先判断两者有没有环，满足题目要求的方法）情况1：如果两个链表都没有环；先遍历两个链表，并记录两个链表的length；两者都走到最后之后，直接判断两个链表最后的节点内存地址是不是相同，相同说明相交，继续走，不同则不相交，返回；相交的话，先让长的那个链表先走diffLength步（因为不可能在长链表的前差值步内相交，不然短的不够长）；然后两个链表同时往下走，直到节点内存地址相同，即是相交点。情况2：如果一个有环一个无环，两者不可能相交（这是单链表，只有一个next）。情况3：两个都有环，会有如下三种子情况：对于子情况2，可以直接按照两个无环链表找相交的问题来处理（需要把入环节点视为终点），对于子情况1和3，找到两个链表的入环节点loop1和loop2，loop2不动，让loop1往下走，如果遇到了loop2，就是子情况1，返回Null；若遇到了loop2，就是子情况2，返回loop1或者loop2都可以。
     • 

Footnotes

1. 快慢指针：快指针一次走两步，慢指针一次走一步，快指针走到结尾，此时慢指针走到中点。意思大概是这么个意思，但是具体走多少，或者更详细的操作，需要具体问题具体分析，有时候也需要给出if等语句。 ↩

2. ↩

3. 两个链表节点相交指的是公用一个节点，即节点的内存地址是相同的，和节点的值是没有任何关系的。单链表只有一个next指针，所以只要相交，后面就一定一样了，不可能相交之后还互相分开 ↩