链表相关的题，给我的第一印象就是指来指去，一个不小心，你就可能晕了。第二印象就是考虑各种边界条件，很烦神烦。第三印象，快慢指针真的是链表里面的一大重要技巧，这种方法是肿么想出来的呢，又适用于什么场景呢？第四个印象，当写了十几道链表题后，后面做起来就跟基本就成了训练自己逻辑思维了，基本上就是敲完代码差不多就能accept了，掌握链表的一些常规技巧，熟悉那种写链表题的感觉很重要呢。
指来指去，指晕了怎么办？
对于单链表而言，结构很简单：
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
而一种基础的操作无外乎就是p.next = q, 意思就是无外乎就是p节点的next引用指向了q。虽然看起来很简单，但链表反转，链表合并之类的东东无外乎就是由这样指来指去的代码，加上一些循环控制构成的。而在这个基础上，如果你实在晕了，我建议画个小图吧，如下图:
linkedlist.jpg
印象二 加个哨兵，世界都变亮了
这种技巧简直了，链表又尼玛的指来指去，动不动还要考虑null值，所以伪造一个空节点指向头节点，让所有的节点都变成拥有前置节点的节点了，简直把操作统一的不要不要的，省的判断来判断去的，不仅简便，让你写的代码也不容易出错。dummy节点，居家必备，好吃不贵（就new一个节点嘛，而且也不用管它，方法执行完了，它就可以被自动销毁了）。
快慢指针法
快慢指针法经典题无疑就是判断单链表有木有环了，但为什么会想到用快慢指针去解题呢，因为如果有环的话，跑的快的就会和跑的慢的相遇？但这其实这更多的是想到用快慢指针后证明这样是可行的，而不是为什么想到快慢指针。
记得当时我第一次碰到这个题，我当时的思路应该是这样的，单链表嘛，能做的操作无外乎就是一直next，去遍历链表(读)，或者就是把节点指针置空或者为null（写），然后判断有木有环好像和写没什么关系，所以看看读把，它如果一直next，那么有环的话就在圈子里打转转，也就是说会遇到之前遍历过的节点，那我就存储下遍历的节点，如遇到相同的就说明还有环了？不过意味着需要拿O(N)的空间复杂度干这件事，而且如果知识数组存的话，空间复杂度会成为O(N)，超时报警肿么办。存太多了，我存少点，行不行，我在它走好远的时候进入了环，我就存一个指针，然后我就继续走，每次和它比较是不是一样。但这个思路在于你都不知道有木有环，你怎么进环。那为了让它有可能进环，它除了也继续往前走好像也没有什么办法，但如果你走一步，我走一步，那走了白走，要不就嘿嘿嘿（其实我想了好久，真心佩服那些在面试中，碰到这种需要创造性性思维的题还能解决的人）。说了这么多，其实是想说不要光想着这个题可以用这个套路，也应该想想为嘛会有这个套路呢，让自己更上一个台阶，能够自己造套路就更棒棒哒了。
说完了这道题，顺便讲下它的延申，求带环链表的入环点，这道题又厉害了，腾讯面试的时候，我碰到这道题，表示很懵逼，但我的思路是因为我要知道精确的入环点，如果要从节点特征的角度上看，那就必须把环中节点全部存储起来，并且遍历链表，直到找到一个节点，它是环中节点，但这意味着要存储环中所有节点，并且每次都需要比较（当然用hash进行比较，也没有什么问题）。有什么其他的思路呢，这个时候由于上一题我们知道了快慢指针分别走了多少次相遇，那么是不是可以通过解方程的形式，把入环前的长度给求解出来呢？不幸的是，我死都凑不齐n元n次方程组，无果，去看答案，表示竟然不用解出来，而是得到一个等式，证明两个指针分别从上一题中快慢指针的相遇点，以及起点出发，能相遇到入环点。呵呵哒，我活该做不出来，但我真心敬佩那些能想到这种方法的人。。。。牛逼。。。。
参考
即刻时间，算法专栏 https://time.geekbang.org/column/126
网友评论