内容简介：

查找
假设有如下这样一个有序链表：

想要查找 24、43、59，按照顺序遍历，分别需要比较的次数为 2、4、6
目前查找的时间复杂度是 O(N)，如何提高查找效率？
很容易想到二分查找，将查找的时间复杂度降到 O(LogN)
具体来说，我们把链表中的一些节点提取出来，作为索引，类似于二叉搜索树，得到如下结构：

这里我们把 10、30、50、80 提取出来作为一级索引，这样搜索的时候就可以使用二分查找来减少比较次数了。
我们还可以再从一级索引提取一些元素出来，作为二级索引，变成如下结构：

比如如果想要查找 59，那么搜索路径就是下面这样的：

回顾下链表的定义：
class ListNode {
private int val;
private ListNode next;
...

查看原文

? 如何用 30s 给面试官讲清楚跳表