博主决定认真刷题～～～
142. Linked List Cycle II
Total Accepted: 70643 Total Submissions: 224496 Difficulty: Medium
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.
Follow up:
Can you solve it without using extra space?现在有两个指针，第一个指针，每走一次走一步，第二个指针每走一次走两步，如果他们走了t次之后相遇在K点
那么 指针一 走的路是 t = X + nY + K ①
指针二 走的路是 2t = X + mY+ K ② m,n为未知数
把等式一代入到等式二中, 有
2X + 2nY + 2K = X + mY + K
=> X+K = (m-2n)Y ③
这就清晰了，X和K的关系是基于Y互补的。等于说，两个指针相遇以后，再往下走X步就回到Cycle的起点了。这就可以有O(n)的实现了。
/** * Linked List Cycle II * Given a linked list, return the node where the cycle begins. If there is no cycle, return null. * Note: Do not modify the linked list. * Tag : Linked List Two Pointers * Similar Problems: (M) Linked List Cycle (H) Find the Duplicate Number * * Analysis: * fast point: 2d = x + y + mC * slow point: d = x + y + nC * x + y = (m - 2n) * C*/public class LinkedListCycle_2 { public static ListNode detectCycle(ListNode head) { if (head == null || head.next == null) { return null; } ListNode fast = head; ListNode slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (fast == slow) { break; } } if (slow == fast) { fast = head; while (slow != fast) { slow = slow.next; fast = fast.next; } return slow; } else { return null; } } public static void main(String[] args) { ListNode res = new ListNode(1); res.next = new ListNode(2); res.next.next = new ListNode(3); res.next.next.next = new ListNode(4); res.next.next.next.next = new ListNode(5); res.next.next.next.next.next = new ListNode(6); res.next.next.next.next.next = res.next.next.next; System.out.print(detectCycle(res).val); }}Status API Training Shop Blog About© 2016 GitHub, Inc. Terms Privacy Security Contact Help