力扣：链表相交、环形链表、环形链表||

力��� 面试题 02.07.链表相交

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

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

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

题解：

如果A、B至少一个为空，则肯定不能相交。

若A、B都不为空，新建一个节点p，使p=headA，再新建一个节点q，使q=headB，同时更新p和q，若p不为null，则p=p.next，否则p=headB，，若q不为null，则q=q.next，否则q=headA，若p==q，则返回p或者q。

完整Java代码如下：

public class Solution {    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {        if(headA == null || headB == null){            return null;        }        ListNode p = headA;        ListNode q = headB;        while(p != q ){            p = p == null? headB : p.next;            q = q == null? headA : q.next;        }        return p;    }}

力扣 141.环形链表

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

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

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1输出：true解释：链表中有一个环，其尾部连接到第二个节点。

题解：

定义两个指针，快指针fast和慢指针slow，使fast=head，slow=head，快指针每次移动两个节点，慢指针每次移动一个节点，如果快慢指针中途相遇，那么这个链表有环。

完整的Java代码如下：

public class Solution {    public boolean hasCycle(ListNode head) {        ListNode low = head;        ListNode fast = head;        while(fast != null && fast.next != null){            low = low.next;            fast = fast.next.next;            if(low == fast){                return true;            }        }        return false;    }}

力扣 142.环形链表||

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

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

不允许修改 链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1输出：返回索引为 1 的链表节点解释：链表中有一个环，其尾部连接到第二个节点。

题解：

第一步判断是否存在环，这个思路个141的思路完全一样。

第二步，如果存在环，找出入环的第一个节点，如何找出第一个节点呢？

思路：从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是环形入口的节点。

完整Java代码如下：

public class Solution {    public ListNode detectCycle(ListNode head) {        ListNode low = head;        ListNode fast = head;        ListNode start = head;        int flag = 0;        while(fast != null && fast.next != null){            fast = fast.next.next;            low = low.next;            if(low == fast){                start = low;                flag = 1;                break;            }        }        if (flag == 1){            ListNode index = head;            if(start == index){                return start;            }            while(start != index){                start = start.next;                index = index.next;                if(index == start){                    return start;                }            }        }        return null;    }}

附：以上题解参考于官方题解以及代码随想录，若有侵权，将在第一时间删除，若有错误，将在第一时间修改。