【云+社区年度征文】LeetCode中链表类题目解析
原创
引言
链表是以节点（node）存储的链式存储结构，一个node包含一个data域（存放数据）和一个next域（存放下一个node的指针），链表的各个节点不一定是连续的，它可以分为带头结点和不带头结点。头结点仅包含next域。
在这篇文章中，主要讲解使用链表的小技巧，如何使用这些技巧来解题，深入解析了LeetCode中具有代表性的链表题目，相信我，看了这篇文章，你再也不用担心关于链表的题目了。
1、链表的几个概念讲解
事实上，链表的结构比较简单，阻碍我们理解链表的常常是因为链表的指针、边界问题等，这有时会让我们很烦躁，不要慌，我们下面一一对这下概念解析，相信你看了会有收获。
1.1链表中的的指针是什么
我们学习C语言时，学过指针，它描述的是指向一个内存地址，在Java语言中，是不存在指针的，但是我们可以把它理解为引用。
当我们将某个变量（对象）赋值给指针（引用），实际上就是将这个变量（对象）的地址赋值给指针（引用）。
p—>next = q; //表示p节点的后继指针存储了q节点的内存地址。
p—>next = p—>next—>next; //表示p节点的后继指针存储了p节点的下下个节点的内存地址。1.1指针指向哪儿
我们写链表代码时，使用的指针的指来指去，很快就把我们搞糊涂了，在这种情况下很容易发生指针丢失和内存泄漏。我们先普及下这两个概念：
指针丢失：自己定义的指针不知道指到哪里了，没有明确的指向。
内存泄漏：链表中的节点没有确切的指针判断，运行时会抛出空指针异常。
我们以插入节点和删除结点来分析指针丢失和内存泄漏的具体情况
- 插入节点
在节点a和节点b之间插入节点x，b是a的下一节点，p指针指向节点a，
p—>next = x;
x—>next = p—>next; 这样的代码会造成指针丢失和内存泄漏，因为这会导致x节点的后继指针指向了自己本身。
正确代码应该为：
x—>next = p—>next;
p—>next = x;
删除节点 同样的，在节点a和节点c之间删除节点b，b是a的下一节点，p指针指向节点a，正确的代码应该为：
p—>next = p—>next—>next;
在删除节点，考虑到删除的节点可能是链表中的第一个节点，我们通常在链表头部加入哨兵(头结点)，这样可以使得删除链表的代码是一致的，不用再额外考虑是否是第一个节点的情况。
在链表加入哨兵的代码为：
//定义一个哨兵作为传入链表的头结点
ListNode pre =new ListNode(0);
pre.next=head;
1.3判断条件
处理链表问题时，要充分考虑链表的边界判断条件，通常情况下，我们经常使用以下几种判断条件：
- 如果链表为空时，代码是否能正常工作？
- 如果链表只包含一个结点时，代码是否能正常工作？
- 如果链表只包含两个结点时，代码是否能正常工作？
- 代码逻辑在处理头结点和尾结点的时候，是否能正常工作？
这些判断条件需要结合自己的实际场景来使用
2、必须掌握的几类题目
在上面的学习中，我们对链表的一些易错的概念进行了解析，下面，我们就真正的代码实践，我在LeetCode上刷题时发现，链表题目通常分为以下几类：
- 单链表的反转(LeetCode206)
- 链表中环的检测(LeetCode141)
- 两个有序链表的合并(LeetCode21)
- 删除链表(LeetCode18)
- 删除链表倒数第n个结点(LeetCode19)
- 求链表的中间结点(LeetCode876)
这几类链表题基本涵盖了大部分知识点，在下面的学习中，我们将一一攻克它，相信掌握它们之后，在以后笔试/面试中，更能随心所欲。
2.1单链表反转(LeetCode206)
思路：从前往后将每个节点的指针反向，即.next内的地址换成前一个节点的，但为了防止后面链表的丢失，在每次换之前需要先创建个指针指向下一个节点。
class Solution {
public ListNode reverseList(ListNode head) {
if(head==null||head.next==null){
return head;
}
ListNode p1=head;
//用一个新的链表
ListNode p2=null;
while(p1!=null){
//每次更换指向之前都需要保存下一个节点
ListNode temp=p1.next;
p1.next=p2;
p2=p1;
p1=temp;
}
return p2;
}
}2.2链表中环的检测(LeetCode141)
思路：定义两个指针，p1和p2，指针p1每次走一步，指针p2每次走两步，如果链表中存在环，则必然会在某个时刻满足p1==p2
public class Solution {
public boolean hasCycle(ListNode head) {
if(head==null||head.next==null){
return false;
}
ListNode slow=head;
ListNode fast=head.next;
while(fast!=null&&fast.next!=null){
if(slow==fast){
return true;
}
slow=slow.next;
fast=fast.next.next;
}
return false;
}
}NOTE：对于快指针来说，因为一次跳两步，如果要使用快指针作为判断条件，fast和fast.next都需要判断是否为空。(不可跨级）
2.3两个有序的链表合并(LeetCode21)
思路：可以新创建一个链表用于合并后的结果，合并的条件如下
- 两个链表都不为空
定义一个指针，查找合适的节点并放入新创建链表的下一位置
- 有一个链表为空
将不为空的链表放入新创建链表的下一位置
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1==null){
return l2;
}
if(l2==null){
return l1;
}
ListNode result=new ListNode(0);
ListNode temp=result;
//两个链表都不为空
while(l1!=null&&l2!=null){
if(l1.val<=l2.val){
temp.next=l1;
temp=temp.next;
l1=l1.next;
}
else{
temp.next=l2;
temp=temp.next;
l2=l2.next;
}
}
//有一个链表为空
if(l1==null){
temp.next=l2;
}
else{
temp.next=l1;
}
return result.next;
}
}2.4删除链表(LeetCode18)
思路：可以在链表头加一个哨兵(头结点)，删除链表时先找到删除链表的上一个位置，按照删除规则删除即可。
class Solution {
public ListNode deleteNode(ListNode head, int val) {
if(head==null){
return null;
}
//定义一个哨兵作为传入链表的头结点
ListNode pre =new ListNode(0);
pre.next=head;
ListNode temp=pre;
while(temp!=null){
if(temp.next.val==val){
temp.next=temp.next.next;
break;
}
else{
temp=temp.next;
}
}
return pre.next;
}
}2.5删除链表倒数第 n 个结点(LeetCode19)
思路：删除节点时要利用好哨兵(带头结点的链表)
- 遍历数组的长度count
- 找到要删除节点的前一个位置count-n-1
- 删除节点
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode pre=new ListNode(0);
pre.next=head;
ListNode temp1=pre;
ListNode temp2=pre;
int count=0;
while(temp1!=null){
temp1=temp1.next;
count++;
}
while(count-n-1>0){
temp2=temp2.next;
count--;
}
temp2.next=temp2.next.next;
return pre.next;
}
}2.6求链表的中间结点(LeetCode876)
思路：找出链表中结点的个数count，然后count/2找出中间结点，删除即可。
class Solution {
public ListNode middleNode(ListNode head) {
if(head==null) return null;
ListNode temp=head;
int count=0;
while(temp!=null){
temp=temp.next;
count++;
}
int mid=count/2;
ListNode result=head;
while(mid>0){
result=result.next;
mid--;
}
return result;
}
}Note:实践是检验真理的唯一标准，要真正的学号链表这个知识点，仅仅学理论是不可靠的，我们需要多敲代码，多思考，多写多练，针对抽象的题目，可以举例画图，来辅助的自己的思考。
3、学习链表的体会
1、 函数中需要移动链表时，最好新建一个指针来移动，以免更改原始指针位置。
2、 单链表有带头节点和不带头结点的链表之分，一般做题默认头结点是有值的。
3、 链表的内存时不连续的，一个节点占一块内存，每块内存中有一块位置（next）存放下一节点的地址。
3、 链表中找环的思想：快慢指针，创建两个指针，一个快指针：一次走两步，一个慢指针：一次走一步，若相遇则有环，若指向null则无环。
4、 链表找倒数第k个节点思想：创建两个指针，第一个指针查询链表中结点的个数count，然后count-k确定删除结点的位置，用第二个指针遍历链表到count-n-1个位置。
5、 反向链表思想：从前往后将每个节点的指针反向，即next内的地址换成前一个节点的，但为了防止后面链表的丢失，在每次换之前需要先创建个指针指向下一个节点。
总结
无论学习任何一个知识点，我们都需要在掌握术(使用方法)的基础上，学习道(本源)，学习数据结构与算法也是一样，我们不仅要掌握如何使用它，更要掌握为什么要是用它，相比其它的方法，它有什么优点，难道是时间复杂度低，空间复杂度小，还是它的数据结构适合这个场景等等...
参考文献
[1]王争.数据结构与算法之美
[2]LeetCode中国网站
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
