Leetcode: 160. Intersection of Two Linked Lists
Write a program to find the node at which the intersection of two singly linked lists begins.

Example:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.

Solution:

/**
 * 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) {

        if (headA == null || headB == null) {
            return null;
        }

        ListNode ta; // 用于记录headA链表的尾结点
        ListNode ha = headA;

        // 第一步、找到headA的尾结点
        while (ha.next != null) {
            ha = ha.next;
        }

        ta = ha; // 记录链表headA的尾结点

        // 第二步、将headB接到ta后面
        ta.next = headB;

        // 第三步、判断是否存在环
        // 判断链表是否存在环，办法为：
        // 设置两个指针(fast, slow)，初始值都指向头，slow每次前进一步，fast每次前进二步，
        // 如果链表存在环，则fast必定先进入环，而slow后进入环，两个指针必定相遇。
        // (当然，fast先行头到尾部为NULL，则为无环链表)程序如下：
        ListNode fast = headA; // 每次前进一步
        ListNode slow = headA; // 每次前进二步
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;

            if (fast == slow) { // 如果相遇了就退出来
                break;
            }
        }

        // 没有环的情况
        if (fast == null || fast.next == null) {
            ta.next = null; // 解开拼接好的链表
            return null;
        }
        // 有环的情况
        // 找到环的入口点
        // 当fast若与slow相遇时，slow肯定没有走遍历完链表，而fast已经在环内循环了n圈(1<=n)。
        // 假设slow走了s步，则fast走了2s步（fast步数还等于s 加上在环上多转的n圈），设环长为r，则：
        //
        // 2s = s + nr
        // s= nr
        //
        // 设整个链表长L，入口环与相遇点距离为x，起点到环入口点的距离为a。
        // a + x = nr
        // a + x = (n – 1)r +r = (n-1)r + L - a
        // a = (n-1)r + (L – a – x)
        //
        // (L – a – x)为相遇点到环入口点的距离，由此可知，从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点，
        // 于是我们从链表头、与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。
        slow = headA;
        while (slow != fast) {
            fast = fast.next;
            slow = slow.next;
        }
        ta.next = null;
        return slow;
    }
}