3. 关于链表中的环的问题

这次主要解决的问题有

1. 求环的长度
2. 找到环的起点
3. 起点到环开始的节点的距离

讲解和画图我放在代码注释里了。
并不是严格的数学推导，代码写的也不算严谨。

package linkedlist;

import leetcode.defaultstructure.ListNode;

import java.util.ArrayList;

/**
 * Created by creat on 2018/7/18.
 */
public class FindBeginNode {
    public static void main(String[] args) {
        FindBeginNode findBeginNode = new FindBeginNode();
        ListNode beginNodeInCycle;
        ListNode testNode = findBeginNode.createTestData(10, 5);
        ArrayList firstMetInfo = findBeginNode.findFirstMetNodeAndStepCountSince(testNode);
        ListNode firstMetNode = (ListNode)firstMetInfo.get(0);
        int lengthFromBeginToFirstMetNode = (Integer)firstMetInfo.get(1);
        System.out.println("First met length is " + lengthFromBeginToFirstMetNode);
        beginNodeInCycle = firstMetNode;
        int oneStepPointerMoves = (Integer)findBeginNode.findFirstMetNodeAndStepCountSince(beginNodeInCycle).get(1);
        System.out.println("Cycle length is " + oneStepPointerMoves);
        ArrayList cycleStarterInfo = findBeginNode.getCycleBeginNodeInfo(testNode, firstMetNode);
        ListNode cycleStarter = (ListNode)cycleStarterInfo.get(0);
        Integer nonCycleLength = (Integer)cycleStarterInfo.get(1);
        System.out.println("Cycle starts at " + cycleStarter.val + "th node");
        System.out.println("Non-Cycle length is " + nonCycleLength);
    }

    /**示例List 1,2,3,4,[5],6,7,8,9,10,[5],6,7,8,9,10,[5],6.......
     * 两个游标，一个一次走一步，一个一次走两步。他俩首次相遇点必然在环中
     * 1 2 3 4 [5] 6 7
     * 1 3 [5] 7 9 [5] 7
     * 如果首次相遇后，两个游标继续走，则慢游标走一圈的时候，快游标恰好走2圈
     * 7 8 9 10 5 6 7
     * 7 9 5 7 9  5 7
     * 也就是说，环的长度，就是此时慢游标走的次数
     */
    private ArrayList findFirstMetNodeAndStepCountSince(ListNode testNode) {
        ListNode oneStep = testNode;
        ListNode twoStep = testNode;
        int count = 0;
        while (true) {
            if (oneStep.val == twoStep.val && count != 0) {
                break;
            }
            oneStep = oneStep.next;
            twoStep = twoStep.next.next;
            count++;
        }
        ArrayList list = new ArrayList();
        list.add(oneStep);
        list.add(count);
        return list;
    }

    /** 示例List 1,2,3,4,[5],6,7,8,9,10,[5],6,7,8,9,10,[5],6.......
     * 在环中，从首次相遇点走到环的起点的距离 = 从List的起点走到环的起点的距离
     * 如下图所示，首次相遇地为7号Node,一个游标从1号node走，另一个从7号node走，相遇点恰好是5。
     * 1 2 3  4  5
     * 7 8 9 10  5
     */
    private ArrayList getCycleBeginNodeInfo(ListNode head, ListNode firstMetNode) {
        ListNode node1 = head;
        ListNode node2 = firstMetNode;
        int count = 0;
        while (true) {
            if (count!=0 && node1.val == node2.val) {
                break;
            }
            node1 = node1.next;
            node2 = node2.next;
            count++;
        }
        ArrayList info = new ArrayList();
        info.add(node1);
        info.add(count);
        return info;
    }

    private ListNode createTestData(int totalNodeNum, int circleStartsAt) {
        ArrayList<ListNode> nodes = new ArrayList<>();
        for (int i = 1; i <= totalNodeNum; i++) {
            nodes.add(new ListNode(i));
        }
        for (int i = 0; i < totalNodeNum - 1; i++) {
            nodes.get(i).next = nodes.get(i+1);
        }
        nodes.get(totalNodeNum-1).next = nodes.get(circleStartsAt - 1);
        return nodes.get(0);
    }

    private void printList(ListNode head) {
        int count1 = 0;
        while (count1 < 50) {
            System.out.print(head.val + ", ");
            head = head.next;
            count1++;
        }
    }
}