LeetCode Linked List Cycle

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

题意：如何判断链表是否有环

这是一个经典的问题，后面还有追问：

如果有环，计算环的长度？

找到碰撞点的位置？

 

首先，如何找环，设计两个指针，分别从链表的头节点开始，走一部和走两步，循环一直到走两步指针为空（说明没有环）或者两指针相遇（说明有环）为止。

主要代码：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null)
    		return false;
        ListNode p1,p2;
        p1=head;
        p2=head;
        boolean ifcycle = false;
        while(p2.next!=null&&p2.next.next!=null)
        {
        	p1=p1.next;
        	p2=p2.next.next;
        	if(p1==p2)
        	{
        		ifcycle = true;
        		break;
        	}
        }
        return ifcycle;
    }
}

 如何计算环的长度：如下图：

 第一次相遇时，走两步的指针总共路程为： S(两步)=圆周+S1+S2 ；走一步的指针路程为 S(一步)=S1+S2 ； 所以环长度为 S（两步）-S（一步）

 

如何找到碰撞点的位置：

由于走两步指针的路程为走一步指针所走路程的两倍，S（两步）=2（S1+S2），再根据第二个公式，可以得出S（圆周）= S1+S2 ； 在这个公式中S2这段是重复的，也就是说从碰撞点开始继续向前走到环入口点的距离和从链表头结点走到入口点的距离是相等的。我们只需要设定两个指针分别从头结点和碰撞点开始每次走一步，相遇点就是环入口点。