首页 > 代码库 > LeetCode Linked List Cycle II 超时问题
LeetCode 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?
题目意思很简单，判断链表是否有环，若有，返回环的位置。
一开始，用了原来I的方法，结果会出现超时。
public ListNode detectCycle(ListNode head) { boolean iscycle=false; if (head!=null) { ListNode temp=head; while (!iscycle) { head=head.next; temp.next=temp; temp=head; if (head==null) { return null; }else { if (head.next==head) { return head; } } } } return head; }
后来发现，我这个算法必须遍历完链表。
查看了网上其他方法。如下算法：
对于判断链表是否有环，方法很简单，用两个指针，一开始都指向头结点，一个是快指针，一次走两步，一个是慢指针，一次只走一步，当两个指针重合时表示存在环了。
证明：假设链表有环，环的长度为N,慢指针在起始位置，快指针在位置k（位置从0开始计数），那么快指针只要比慢指针多走经过N-k步，就可以追上慢指针了。。。，因为每一次快指针都比慢指针多走一步，所以一定可以在有限的步数追上慢指针。
成功ac。
/** * 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) { ListNode node = null; if(head == null) return node; ListNode quick = head; ListNode slow = head; boolean tag = false; while(quick!=null &&quick.next != null) { quick = quick.next; quick = quick.next; slow = slow.next; if(quick == slow) { tag = true; break; } } if( tag == false) { return node; } else { quick = head; while( true) { if( quick == slow) { return quick; } else { quick = quick.next; slow = slow.next; } } } }}
LeetCode Linked List Cycle II 超时问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。