一、相交链表

给你两个单链表的头节点?headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

主要思路：

首先我们需要明白，两个链表相交，最重要的是他们有一个结点的地址相同，而不是值。

查找两个链表相交的点，那么就可以先计算出两个链表各自的长度，然后再让较长的那一个链表先走 '两者之间长度之差'的步数，之后两者再一起走，这样就可以判断是否相遇。

代码1：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode cur1 = headA;
        ListNode cur2 = headB;
        int count1 = 0;
        int count2 = 0;
        //计算两个链表各自的长度
        while(cur1 != null) {
            cur1 = cur1.next;
            count1++;
        }
        while(cur2 != null) {
            cur2 = cur2.next;
            count2++;
        }
        cur1 = headA;
        cur2 = headB;
        //记录两个链表长度之间的差值
        int k = 0;
        k = count2 - count1;
        //让链表长度较长的那一端先走k步
        if(k > 0) {
            while(k-- > 0){
                cur2 = cur2.next;
            }
        }else if(k < 0 ){
            k = count1 - count2;
            while(k-- > 0) {
                cur1 = cur1.next;
            }
        }
        //两个链表一起走
        while(cur1 != cur2) {
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur2; 
    }
}

?代码2：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //这里是假设
        ListNode cur1 = headA;//cur1永远指向长的链表
        ListNode cur2 = headB;//cur2永远指向短的链表
        int count1 = 0;
        int count2 = 0;
        //计算两个链表各自的长度
        while(cur1 != null) {
            cur1 = cur1.next;
            count1++;
        }
        while(cur2 != null) {
            cur2 = cur2.next;
            count2++;
        }
        cur1 = headA;
        cur2 = headB;
        //记录两个链表长度之间的差值
        int k = count1 - count2;
        if(k < 0 ) {
            k = count2 - count1;
            cur1 = headB;
            cur2 = headA;
        }
        
        //让链表长度较长的那一端先走k步
        while(k-- > 0) {
            cur1 = cur1.next;
        }
        //两个链表一起走
        while(cur1 != cur2) {
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur2; 
    }
}

题目链接：相交链表

二、环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递?。仅仅是为了标识链表的实际情况。如果链表中存在环?，则返回 true 。否则，返回 false 。

?主要思路：

这道题应采用快慢指针（需要速度差）的方法解题，我们可以把链表的带环部分理解为操场，也就是我们日常中所说的追击问题，两者都进圈时，fast指针最多追一圈（在一圈之内一定能追上）。

代码实现：

/**
 * 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) {
        ListNode slow = head;
        ListNode fast = head;
        //判断链表是否带环
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                return true;
            }
        }
        return false;
    }
}

题目链接：环形链表

三、环形链表——进阶版本

给定一个链表的头节点 ?head?，返回链表开始入环的第一个节点。?如果链表无环，则返回?null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改链表。

?主要思路：

该题是上面题目的进阶版本，但是代码跟上面相差无几，首先思路必须明确：既然是寻找链表的第一个入环的结点，那么就需要先判断链表是否为带环链表。

判断完上述条件后（slow和fast已经在环内相遇），这时需让slow结点返回到起点，之后再同时让slow和fast指针同时走（每次走一步，因为这时各自到入环的第一个结点距离是相等的），当它们相遇时，便是入环的第一个结点。

为什么说上面说，快慢指针各自到入环的第一个结点距离是相等的呢？

理由如下：

?可能有的人会反映：上面是利用特殊情况取巧（快指针在环内已经走了一圈，那如果不是走一圈,是走很多圈呢？）

以下为解释部分：

扩展问题?

注意：

1、慢指针进环之后，快指针肯定会在慢指针走一圈之内追上慢指针

因为：慢指针进环后，快慢指针之间的距离最多就是环的长度，而两个指针在移动时，每次他们之间的距离都会缩减一步，因此慢指针移动一圈之前快指针肯定是可以追上慢指针的。

2、当慢指针进入环内，快指针可能已经在环内绕了n圈，n至少为1

因为：快指针先进环走到M的位置，最后又在M的位置与慢指针相遇。

常问：

为什么快慢指针要设置为一个走两步，一个走一步？

因为：如果快指针设置太快（走三步，走四步），可能会造成在环内两者永远都相遇不了（追上不算相遇），而两步和一步即使在环为1的情况下，也算可以相遇的。

/**
 * 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) {
        //先判断是否有环
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast) {
                break;
            }
        }
        //代码走到这里 要么是while循环中某个条件不满足，要么就是slow和fast相遇
        if(fast == null || fast.next == null) {
            return null;
        }
        slow = head;
        while(slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }
}

题目链接：环形链表进阶版本