Linked List Cycle

Description:

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

问题描述：

检测给定链表是否有环

限定条件：

空间复杂度O（1），不开辟额外空间

解法一：

思路：

先进行空链表检查，循环问题可以看成周期性问题，如果结点总数为n,一个指针走n步必定和一个指针走kn部相遇（如果链表有环）,这里为了简化另k=2。所以可以设定两个指针，一个walker一次走一步，一个runner一次走两步。walker走n步和runner走2n步相遇。

Code:

/** * 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 walker = head; ListNode runner = head; while(runner.next != null && runner.next.next != null){ walker = walker.next; runner = runner.next.next; if(walker == runner) return true; } return false; } }