首页 > 编程语言 > 详细

JAVA-Linked List Cycle I&&Linked List Cycle II

时间:2015-01-07 14:57:37      阅读:306      评论:0      收藏:0      [点我收藏+]

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?

技术分享 
第一题要求是否有环 从图中可以看出 使用快慢指针 只要有环两者必定会相遇  另外从相遇点可以看出 相遇点距离环的起始点的距离与head到起始点的距离是相同的 只要再设一指针 与slow一起走 相遇点即环的起始点 
 若设 环的大小为 a 快慢指针的路程分别为x和y   则  x+a=y , y=2x  ==>x=a;即慢指针走过的路程恰为环的大小  此时从相遇点到环起点恰为整个链表的长度 而从head出发恰好差一个环的距离 所以相遇点必为环的起点 代码如下:
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null||head.next==null) return null;
        ListNode slow=head;
        ListNode fast=head;
        int count=0;
        while(fast.next!=null&&fast.next.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            count++;
            if(slow==fast)  break;
        }
        if(slow==fast&&count!=0){
            ListNode res=head;
            while(res!=slow){
                res=res.next;
                slow=slow.next;
            }
            return res;
        }else{
            return null;
        }
    }
}

JAVA-Linked List Cycle I&&Linked List Cycle II

原文:http://blog.csdn.net/u012734829/article/details/42492201

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!