016.链表高频题目和必备技巧

前置知识：【入门】009~012 的 链表入门内容、归并排序、哈希表的使用、重要排序算法的总结

链表类题目注意点 §

1. 如果笔试中空间要求不严格，直接使用容器来解决链表问题（使用容器的话几乎就很简单了）
2. 如果笔试中空间要求严格、或者在面试中面试官强调空间的优化，需要使用额外空间复杂度 O(1) 的方法
3. 最常用的技巧：快慢指针
4. 巧用哨兵节点可以省去很多边界条件的讨论
5. 链表类题目往往都是很简单的算法问题，核心考察点也并不是算法设计，而是 coding 能力
6. 这一类问题除了多写多练没有别的应对方法

个人建议：链表类问题既然练的就是 coding，那么不要采取空间上讨巧的方式来练习

注意：链表相关的比较难的问题是约瑟夫环问题，会在【扩展】阶段讲解，变形很多会单独出一期视频讲解

题目1.返回两个无环链表相交的第一个节点 §

相交链表

题目2.每 k 个节点一组翻转链表 §

K 个一组翻转链表

题目3.复制带随机指针的链表 §

随机链表的复制

题目4.判断链表是否是回文结构 §

快慢指针找中点

回文链表

这个题的流程设计甚至是考研常用：

把    a -> b -> c -> d -> e
变成  a -> e -> b -> d -> c

题目5.返回链表的第一个入环节点 §

快慢指针

环形链表

证明【来自评论区】：

题目6.在链表上排序 §

要求时间复杂度 $O(n\ast lo{g}^n)$，额外空间复杂度 $O(1)$，还要求排序有稳定性

数组上 无法做到，链表可以（原地归并排序），因为链表是非连续空间，可以不需要辅助空间

排序链表

备注 §

这些题目往往难度标为“简单”，是因为用容器解决真的很简单

但是不用容器、实现额外空间复杂度 O(1) 的方法并不轻松，包括很多提交的答案也都没有符合要求

一定要自己来写一遍，多练！思路看起来简单，难的是 coding