【经验总结】LeetCode中链表类题目经验总结十条

前言

链表是以节点（node）存储的链式存储结构，一个node包含一个data域（存放数据）和一个next域（存放下一个node的指针），链表的各个节点不一定是连续的，它可以分为带头结点和不带头结点。头结点仅包含next域。
在这篇文章中，主要讲解使用链表的小技巧，如何使用这些技巧来解题，并且列举LeetCode中具有代表性的链表题目，这篇文章非常适合已经刷过一定数量链表类题目的uu观看，看完有助于巩固总结做链表这类题目的经验技巧。

干货经验汇总

第一梯队

1、 函数中需要移动链表时，最好新建一个指针来移动，以免更改原始指针位置。

2、 单链表有带头节点和不带头结点的链表之分，一般做题默认头结点是有值的。

3、 链表的内存时不连续的，一个节点占一块内存，每块内存中有一块位置（next）存放下一节点的地址。

3、 链表中找环的思想：快慢指针，创建两个指针，一个快指针：一次走两步，一个慢指针：一次走一步，若相遇则有环，若指向null则无环。

4、 链表找倒数第k个节点思想：创建两个指针，第一个指针查询链表中结点的个数count，然后count-k确定删除结点的位置，用第二个指针遍历链表到count-n-1个位置。

5、 反向链表思想：从前往后将每个节点的指针反向，即next内的地址换成前一个节点的，但为了防止后面链表的丢失，在每次换之前需要先创建个指针指向下一个节点。

第二梯队

6、题解优先看力扣的官方题解。

7、命名方面，最好根据个人习惯默认好命名，不要随便命名，这样可以大大降低失误率，例如临时节点可以命名为temp、当前操作节点cur、前一个节点prev、头节点dummy。

8、从我目前的立场看，链表的题目，但凡涉及删除节点这个操作（这个操作可能作为单独的考点，也可以作为复杂题目的一小步）的题目，都统一设置虚拟化头节点会很方便，因为这样原链表的所有节点就都可以按照统一的方式进行移除了。另一方面，设置虚拟头节点后，其next总是head，在一些链表题目中也非常方面返回操作后的新链表的头节点。

9、充分理解节点赋值和节点指向的意思，不要混淆了，例如ListNode prev =cur,这是单纯的赋值，不是讲prev这个节点的next指向cur的意思，这个一定要明确。然后例如ListNode prev = head,那么prev的一些操作就是会同步到head的，赋值就是两个一样了。

10、很多如果只涉及链表中值val规律的，例如判断是否是回文链表、是否有环以及找到环链表尾节点指向的链表索引位置等等，都可以通过哈希表方便的做出来。

其他：加哨兵前，链表的头节点head就是可能为null的，但是加了哨兵后，它绝不可能为空，但是它的value是不会被用的，只是一个指示作用，总是指向我们实际数据的第一个数据。

无论各种实现，例如单向链表、双向链表、环形链表等等，其最终的刚开始的初始化实现，基本思想都是先把哨兵的值初始化，其pre或者next都是先设置为null，然后再无参构造里面根据不同结构的特点然后对pre和next进行赋值。

力扣代表性链表题目推荐

E01. 反转单向链表-Leetcode 206
E02. 根据值删除节点-Leetcode 203
E03. 删除倒数节点-Leetcode 19
E04. 有序链表去重-Leetcode 83
E05. 有序链表去重-Leetcode 82
E06. 合并有序链表-Leetcode 21
E07. 合并多个有序链表-Leetcode 23
E08. 查找链表中间节点-Leetcode 876
E09. 回文链表-Leetcode 234
E10. 环形链表-Leetcode 141
E11. 环形链表-Leetcode 142
E12. 删除节点-Leetcode 237
E13. 共尾链表-Leetcode 160