思路：
1.分别求出这两个链表的长度
2.创建两个引用，指向两个链表的头节点；找到长度长的链表，让她的引用先走差值步数
3.让这两个引用，同时往后走，每个循环各自走一步
然后再判定两个引用是否指向同一个节点，如果发现相同，那么就说明该节点就是链表的交点
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public int size (ListNode head){
int size =0;
for(ListNode cur = head;cur != null;cur = cur.next){
size++;
}
return size;
}
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//1.首先求出两个链表各自的长度
int sizeA=size(headA);
int sizeB =size(headB);
//2.判断谁更长 让更长的链表先走
ListNode A = headA;
ListNode B = headB;//A和B要提前声明，否则后期找不到他们！
if(sizeA >sizeB){
//A先走差值的步数
int countA = sizeA - sizeB;
while(countA != 0){
A = A.next;
countA--;
}
}else{
//B先走
int countB = sizeB - sizeA;
while(countB != 0){
B = B.next;
countB--;
}
}
//3.然后让这两个引用各自往后走
while(A != null && B != null){
if( A == B){
return A;
}
A = A.next;
B = B.next;
}
return null;
}
}
解法1：遍历链表，每次遍历一个节点，就把这个节点的引用存到一个LIst里面，遍历下一个节点的时候，判定下一个节点是否在List中已经存在过了。如果发现某个节点已经在List里面有了，并且又再次遍历到了，认为这个链表是带环的。
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
//1.首先判断链表是否为空
if(head == null){
return false;
}
//2.创建一个顺序表
List<ListNode> list = new ArrayList<>();
//3.对链表进行遍历
for(ListNode cur = head ; cur != null ;cur = cur.next){
//判断一下给的节点的引用是否存在？
if(list.contains(cur)){
return true;
}
//如果不存在 那就继续循环
list.add(cur);
}
return false;
}
}然而，上面这种解法的时间复杂度为O（N^2），适合在线笔试的时候用，因为她比较好想。
更好的方法为双指针法：
首先创建两个引用，都指向链表的头部，其中一个引用fast，一次循环，往后走两步
另一个引用slow，一次循环，往后走一步
如果链表不带环，此时这两个引用永远不会重合
如果带环，就会有重合的一天
空间复杂度为O（1），时间复杂度为O（N）（*考虑极端情况，比如环的长度就是整个链表长度N，fast和slow最开始上环的时候，差距是N，此时意味着，每循环一次，差距就措施小N，最多经过N次就重合了）
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
//应用双指针法来进行解题
//首先判断特殊情况
if(head == null){
return false;
}
//创建快慢指针
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
//判断二者是否指向同一个地址
if(slow == fast){
return true;
}
fast = fast.next.next;
slow = slow.next;
}
return false;
}
}扩展延申：
当前是fast一次走两步，slow一次走一步，可以判定是否带环
假设fast一次走三步/四步/五步/，slow一次走一步，能否判定出是否带环呢？
结论是否定的。
反例：fast一次走3步，slow一次走1步，环的长度为2，这样的情况下，fast和slow是永远也重合不了的，这和环的长度是有关系的。
规律总结：如果fast和slow的差值为N，此时给长度为N的环，那永远也重合不了~
只有说，fast和slow的差值为1的时候，才是最保险的！
解法：应用快慢指针法来解答这一道题
首先找到slow和fast交汇的位置
创建cur1从交汇位置出发，创建cur2从链表的头部出发，每次循环走一步的方式，同时往后走，当cur1与cur2重合，此时相遇的位置，就相当于环的入口
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
//1.首先判断链表是否为空
if(head == null){
return null;
}
//2.然后再使用快慢指针判断有环or无环
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
fast =fast.next.next;
slow = slow.next;
//应该在这里进行判断
if(fast == slow){
break;
}
}
//3.判断是因为哪种情况出来的
if(fast == null || fast.next == null){
return null;
}
//4.使用cur2，cur1分别从头和相交处开始走
ListNode cur2=head;
ListNode cur1 =fast;
while(cur1 != cur2 ){
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
}
} ArrayList和LinkedList的区别
