142. Linked List Cycle II

[Shawngbk]

复杂度O(n)的方法，使用两个指针slow,fast。两个指针都从表头开始走，slow每次走一步，fast每次走两步，如果fast遇到null，则说明没有环，返回false；如果slow==fast，说明有环，并且此时fast超了slow一圈，返回true。 与141类似 /**

• 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) return null; ListNode first = head; ListNode second = head; boolean hasCycle = false; while(second.next != null && second.next.next != null) { first = first.next; second = second.next.next; if(first == second) { hasCycle = true; break; } } if(!hasCycle) { return null; } //因为second是second.next.next，所以second回到原点，要把first也放回原点 first = head; while(first != second) { first = first.next; second = second.next; } return first; } }