方法1：求出长度差统一起始点来遍历判断。
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { //求出长度差值进行判断 int countA=0; int countB=0; ListNode a=headA; ListNode b=headB; //求a链表的长度 while(a!=null){ countA++; a=a.next; } //求b链表的长度 while(b!=null){ countB++; b=b.next; } //重置a，b a=headA; b=headB; //如果B更长就交换它们 if(countB>countA){ int temlen=countA; countA=countB; countB=temlen; ListNode temNode=a; a=b; b=temNode; } //求长度差 int x=countA-countB; //让a和b同一起跑线（末尾对齐） while(x-->0){ a=a.next; } //同时遍历a和b，遇到相同则返回 while(a!=null){ //是a==b而不是a.var==b.var if(a==b) return a; a=a.next; b=b.next; } //没找到返回Null return null; } }
方法2：我们知道，A和B链表长度可能是不等的，但链表A+B和B+A的长度却是相等的。如果A和B的结尾具有相同的节点，那么A+B和B+A也会有相同的，这样我们就能克服长度不同的困难。
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode a=headA; ListNode b=headB; //a==b时要么找到了相等，要么两者同时遍历完都为null（都为null时也是相等的情况，所以不会死循环，因为遍历的长度都相等，所以最后没找到相同的情况下，它们会最后同时为null） while(a!=b){ //如果A遍历完则接着遍历B a=a!=null?a.next:headB; //如果B遍历完则接着遍历A b=b!=null?b.next:headA; } //这里a或b都可以。当二者都为null出来说明没有相同的节点，否则就是找到了相同节点 return a; } }
🌿7.环形链表（简单）
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
题目链接：环形链表https://leetcode-cn.com/problems/linked-list-cycle/
方法1：利用HashSet存储遍历过的节点，如果判断到已存储过返回直接返回true，遍历完的话返回false（时间复杂度O（N），空间复杂度O（N））
public class Solution { public boolean hasCycle(ListNode head) { Set<ListNode> set=new HashSet<ListNode>(); ListNode a=head; while(a!=null){ if(!set.contains(a)){ set.add(a); }else{ //说明回到了环起点，有环 return true; } a=a.next; } //遍历完无重复节点，无环 return false; } }
方法2龟兔赛跑：其实也是快慢双指针方法，如果链表成环，快指针肯定会因为速度比慢指针快从而超过慢指针一圈而赶上慢指针。如果快指针跑到终点为接近null，说明这个链表就无环。
public class Solution { public boolean hasCycle(ListNode head) { if(head==null||head.next==null) return false; //快指针需要在慢指针右边，这样才会进入下面while循环体 ListNode slow=head; ListNode fast=head.next; while(slow!=fast){ //如果fast后面即将为null说明到了链表尾部返回false，链表无环 if(fast==null||fast.next==null) return false; fast=fast.next.next; slow=slow.next; } //跳出循环了说明slow==fast，快指针追上了慢指针，链表有环 return true; } }
🌿8.环形链表||（中等）
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改链表。
题目链接：环形链表||https://leetcode-cn.com/problems/linked-list-cycle-ii/
与上一题类型，只不过返回值不一样了，所以大部分方法是通用的。
方法1：同理与上一题的方法1，用HashSet遍历，找到已存储过的节点就是环的起点，直接返回即可。
public class Solution { public ListNode detectCycle(ListNode head) { Set<ListNode> set=new HashSet<ListNode>(); ListNode a=head; while(a!=null){ if(!set.contains(a)){ set.add(a); }else{ //已经存储过，说明这就是环起点 return a; } a=a.next; } //遍历结束，说明无环 return null; } }
方法2双指针：同理于上一题的双指针思想，但这一题会有点难度，需要一定的数学归纳证明。同样第一次快慢指针相遇后可判断到有环。此时将快指针重置到head，然后和慢指针一样一次走一格，当他们二次相遇时，会在环的入口。这里贴上一篇数学归纳的证明链接：双指针法
public class Solution { public ListNode detectCycle(ListNode head) { if(head==null||head.next==null) return null; ListNode slow=head; ListNode fast=head; while(true){ //说明无环直接返回null if(fast==null||fast.next==null) return null; fast=fast.next.next; slow=slow.next; //第一次相遇 if(slow==fast) break; } fast=head; while(fast!=slow){ slow=slow.next; fast=fast.next; } return fast; } }
🎨3.链表专题总结
通过上面的题目其实我们很容易总结出一些做题的套路和技巧。1.就是设置虚拟头结点。因为在链表中头结点的处理往往比较特殊，通过设置虚拟头结点能帮助我们统一操作。2.手动迭代过程。链表类的题目最忌讳靠脑子去凭空想象，特别是初学阶段，自己演示流程，才能写出逻辑清晰的代码。3.多搭配双指针算法。通过上面的专题训练，可以很容易看出链表和双指针搭配的比重很大，所以做题时往往可以考虑双指针算法是否可行。4.反复训练，多加练习。这点也是最重要的，这套题大家可以反复训练加深印象，同时去力扣寻找更多的链表题目进行训练。相信有了这套专题，以后面试一定能手撕代码！
