首页 > 代码库 > LeetCode OJ - Linked List Cycle II
LeetCode OJ - Linked List Cycle II
题目:
Given a linked list, return the node where the cycle begins. If there is no cycle, return null
.
Follow up:
Can you solve it without using extra space?
解题思路:
设置两个指针slow和fast,从head开始,slow一次一步,fast一次两步,如果fast能再次追上slow则有圈。
设slow走了n步,则fast走了2*n步,设圈长度m,圈起点到head距离为k,相遇位置距离圈起点为t,则有:
n = k + t + pm; (1)
2*n = k + t + qm;(2)
这里p和q是任意整数。(不过fast速度是slow二倍,则肯定在一圈内追上,p就是0了)
2 * (1) - (2) 得k = lm - t;(l = q - 2 * p)
即 k 的长度是若干圈少了 t 的长度。
因此这时候,一个指针从head开始,另一个从相遇位置开始,都每次只走一步,当从head开始的指针走到圈开始位置时,两指针刚好相遇。
代码如下:
/** * 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 fast = head, slow = head; do { fast = fast.next; if (fast != null) { fast = fast.next; } else { return null; } if (fast == null) return null; slow = slow.next; }while (fast != slow); ListNode behind = head, front = slow; while (behind != front) { behind = behind.next; front = front.next; } return behind; } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。