Leetcode.142-Linked-list-cycle-ii(环形链表II)

环形链表II

思路 https://www.cnblogs.com/springfor/p/3862125.html

https://blog.csdn.net/u010292561/article/details/80444057

假设周长为 S

AB + BC + n*S = 2 * ( AB + BC )

=> AB = BC + n*S

只要知道了 C 点， 就可以知道 B点了。C点通过快慢指针获得，然后 让一个指针在A点出发，另外一个在C点出发，经过 n 圈，相遇的点就是 AB 点。

  /**

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

            if (null == head || null == head.next) {

                return null;

            }

            ListNode p1 = head;

            ListNode p2 = head;

            boolean sign = false;

            while (null != p2 && null != p2.next) {

                p1 = p1.next;

                p2 = p2.next.next;

                if (p1 == p2) {

                    sign = true;

                    break;

                }

            }

            p1 = head;

            if (sign) {

                while (p1 != p2) {

                    p1 = p1.next;

                    p2 = p2.next;

                }

                return p1;

            } else {

                return null;

            }

        }

    }

　　

Leetcode.142-Linked-list-cycle-ii(环形链表II)的相关教程结束。