微软面试真题+面试官改编 leetcode 思路（链表篇）

[longSwordMan]

在上一篇文章与大家分享了动态规划篇，今天想继续跟大家探讨一下链表篇。

链表是一个非常经典的数据结构，但是也非常 tricky，而且常见的是令人虎躯一震的空间 in place 要求，由于链表的一些特殊性质，经常会作为一个面试考察的重点。

我们先看一个原题： 从已排序的链表中移除重复的单元，如 1->1->2, 返回 1->2. 1->1->2->3->3, 返回 1->2->3

思路很简单，双指针，指针往后找，碰到相同的数值，继续往后，直到第一个不同的数，讲慢指针的 next 指向快指针，得解。关键在于 one pass，一次过，如果搞个哈希表来做那是画蛇添足，空间上不是最优解，而空间的考察其实是链表的重中之重，所以这就是我一直强调的，哈希虽好，但要慎用。

改编题 1： 给定有序链表，如果某元素出现三次以上的，删除该元素，1->1->2->3->3->3, 返回 1->1->2 我们仍然可以双指针，如果数值不同，快慢指针各走一步 遇到相同数值，快指针继续走，同时计数，超过三次就接着往后，碰到新数字后修改慢指针的 next 。

改编题 2： 但如果改成无序的链表呢？ 题目变成：给定无序链表，如果某元素出现三次以上的，删除该元素。 这时候我们要头脑冷静地分析，条件虽然变了，但和之前的题目有什么关联和不同？ 这时候不是有序数组，因此相同的数不会团在一起，为了能够方便判断是否有 3 个以上的频次，我们需要借助哈希表去统计出现的频次，key 是链表元素的 value，值是频次。那么第二次遍历的时候，我们把链表的 value 当作 key 去哈希表查找，如果对应值大于三，删除元素，问题得解。算法时间复杂度 O （ n ），空间 O （ n ）。

改编题 3： 无序链表，但如果要求重复元素的个数不超过自身的 value 呢，比如：1-> 1-> 2->3->2->2 改成：1 - 2 - 3 - 2 还是用哈希，只不过需要厘清几个值的关系，该 map：key 是链表的 value，value 是链表 value 出现的频次。循环的时候，第一次遍历统计频次，第二次遍历，如果 map （ node.val ）> node.val ，删一个节点，并且同时 map 中的 node.val 值减一，算法时间复杂度 O （ n ），空间 O （ n ）得解。

其他推荐原题： 两链表交叉点问题 链表环问题 链表 merge sort 问题

这几个经典原题原题的改变我之后在我的荔枝微课直播间都会提及。 可以加微信 longswordMAN 进群+听直播，注明 V2EX 的 id 即可。