寻找链表的入环节点和相交节点问题
作者：Grey
原文地址：
判断链表中是否有环
给你一个链表的头节点 head ，判断链表中是否有环。
题目链接见：LeetCode 141. Linked List Cycle
主要思路
使用快慢指针，从链表头开始，快指针(fast)一次走两步，慢指针(slow)一次走一步，如果快指针会走到 null，则说明无环；否则有环，而且有环情况下，快慢指针必在某个位置相遇，即：slow == fast。
完整代码如下
public class Solution { public static boolean hasCycle(ListNode head) { if (null == head || head.next == null) { return false; } ListNode fast = head.next.next; ListNode slow = head.next; if (fast == null) { return false; } if (fast.next == null) { return false; } while (fast != slow) { fast = fast.next.next; if (fast == null || fast.next == null) { return false; } slow = slow.next; } return true; } } 链表开始入环的第一个节点
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
题目链接见：LeetCode 142. Linked List Cycle II
主要思路
使用快慢指针，从链表头开始，快指针一次走两步，慢指针一次走一步，如果快指针会走到 null，则说明无环；
如果有环，则快指针和慢指针必在某个节点相遇，假设在 m 节点相遇，然后快指针回到链表头节点，慢指针停留在 m，
接下来继续：
快指针一次走两步；慢指针一次走一步。
快慢指针再次相遇的点就是第一个入环节点。
完整代码如下
public class Solution { public static ListNode detectCycle(ListNode head) { if (head == null || head.next == null || head.next.next == null) { return null; } // 1. 快指针一次走两步，慢指针一次走一步 // 2. 如果无环，快指针一定会走到空 // 3. 如果有环，快指针和慢指针一定会在某处相遇。 // 4. 相遇后，快指针回到原点，慢指针保持在原地 // 5. 快慢指针同时每次走一步，一定在入环处相遇 ListNode fast = head; ListNode slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; // 第一个相遇节点 if (fast == slow) { break; } } // 一定无环 if (fast == null || fast.next == null) { return null; } // 快指针回到头节点 // 慢指针停留在原处 if (fast == slow) { fast = head; } while (fast != slow) { fast = fast.next; slow = slow.next; } return fast; } } 两个链表相交的起始节点
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
注：本题中保证整个链式结构中不存在环。
题目链接：LeetCode 160. Intersection of Two Linked Lists
主要思路：
如果两个链表是相交的，则两个链表的最后一个节点一定是一样的，如果两个链表最后一个节点不一样，则一定不相交。
先获取两个链表的长度，将其中长度更长的链表设置为 bigger，长度为 len1；更短的链表设置为 smaller，长度为 len2。
两个链表长度的差值 gap = len1 - len2，接下来，分别设置两个指针指向 bigger 链表头部和 smaller 链表的头部，
先让 bigger 链表的头部指针走gap步，然后 bigger 指针开始和 smaller 指针同步走，如果两个链表相交，则一定在相交的起始节点相遇，如果不相交，则两个链表会走向 null 节点（由于题目已经确保了链式结构中不存在环）。
如下示例图，其中 smaller 和 bigger 链表如下，x 节点是相交节点
先让 bigger 链表走两步
然后 bigger 和 smaller 分别从 h2 和 h1 开始走，一定会在 x 相遇。如下图
完整代码如下
public class Solution { public static ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (null == headA || null == headB) { return null; } if (headA.next == null && headB.next == null) { return headA == headB ? headA : null; } int lenOfA = getLen(headA); int lenOfB = getLen(headB); ListNode bigger = lenOfA > lenOfB ? headA : headB; ListNode smaller = bigger == headA ? headB : headA; int gap = Math.abs(lenOfA - lenOfB); while (gap != 0) { bigger = bigger.next; gap--; } while (bigger != null && smaller != null) { if (bigger == smaller) { return bigger; } bigger = bigger.next; smaller = smaller.next; } return null; } public static int getLen(ListNode head) { int len = 0; while (head != null) { len++; head = head.next; } return len; } } 
