为云计算团队制定IT接任者计划
|
这两个方法孰优孰劣呢？ 网上很多说什么方法一过了两遍链表，方法二只过了一遍。 但其实，但是方法二用了两个指针来遍历，所以两个方法过的遍数都是一样的。 它们最大的区别是： 方法一是 offline algorithm，方法二是 online algorithm。 公司里的数据量是源源不断的，比如电商系统里总有客户在下单，社交软件里的好友增长是一直在涨的，这些是数据流 data stream，我们是无法计算数据流的长度的。 那么 online algorithm 能够给时刻给出当前的结果，不用说等数据全部录入完成后，实际上也录不完。。这是 online algorithm 比 offline algorithm 大大的优势所在。
更多的解释大家可以参考 stack overflow 的这个问题，链接在文末。 这题就是给一个链表，然后找到它的中点，如果是奇数个很好办，如果是偶数个，题目要求返回第二个。 比如： 1 -> 2 -> 3 -> 4 -> 5 -> NULL，需要返回 3 这个 ListNode； 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL，需要返回 4 这个 ListNode。 但其实吐槽一下，如果真的要设计一个这样的 API，我更倾向于选择返回偶数个中的第一个中点。 为什么呢？ 算法题都是工业生产中一些问题的抽象。比如说我们找中点的目的是为了把这个链表断开，那么返回了 3，我可以断开 3 和 4；但是返回了 4，单向链表我怎么断开 4 之前的地方呢？还得再来一遍，麻烦。 Solution 方法一、
这题最直观的解法就是可以先求这个链表的长度，然后再走这个长度的一半，得到中点。 其实链表相关的题目没有很难的，套路也就这么几个，其中最常考最基础的题目是反转链表，听说微软可以用这道题电面刷掉一半的 candidate，两种方法一遍 bug free 还是不容易的。文章之前已经写过了，点击这里直达复习。 今天我们来说链表中最主要的 2 个技巧：双指针法和 dummy node，相信看完本文后，链表相关的绝大多数题目你都能搞定啦。 双指针法 双指针法在很多数据结构和题型中都有应用，在链表中用的最多的还是快慢指针。 顾名思义，两个指针一个走得快，一个走得慢，这样的好处就是以不同的速度遍历链表，方便找到目标位置。
常见的问题比如找一个链表的中点，或者判断一个链表是否有环。 （编辑：四平站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
