LeetCode：Linked List Cycle II

试题：
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.
Example 2:
Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.
Example 3:
Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list
Follow up:
Can you solve it without using extra space?
代码：
LeetCode：Linked List Cycle II
1、单链表有环，那么进入环内的指针只能在环内移动；
2、如果指针p1每次走一步，而p2每次走两步，那么p1和p2一定会在环内相遇，以此判断有环；物理题：两人速度相差为1，绕圈跑。
3、而且p2不需要再跑完一圈就能追上p1，因为p1到达入口时，p2与p1距离不足一圈，只要再跑距离差就能追上。
4、那如何判断环的入点?p2的速度是p1速度的两倍，当p1和p2相遇时，p2比p1多跑一倍距离。也就是说p2跑了2(s+r)=s+r+n*(r+l)距离（C为相遇点，n为跑的圈数），显然n=1，s=l，n>1时走s的距离相当于在圈内跑n-1圈+l的距离，刚好又到入口点s=(n-1)(r+l) + l

/**
 * 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 (head == null || head.next == null) return null;

        ListNode firstp = head;
        ListNode secondp = head;
        boolean isCycle = false;

//         遍历链表知道
        while(secondp != null) {
//             走一步
            firstp = firstp.next;
//             如果secondP走到底那就说明没环
            if (secondp.next == null) return null;
//             走两步
            secondp = secondp.next.next;
            if (firstp == secondp) { isCycle = true; break; }
        }

        if(!isCycle) return null;
        firstp = head;
        while( firstp != secondp) {
            firstp = firstp.next;
            secondp = secondp.next;
        }

        return firstp;
    }
}

LeetCode：Linked List Cycle II

相关推荐