首页 > 代码库 > 142. Linked List Cycle II

142. 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.

Follow up:
Can you solve it without using extra space?

给定一个链表的头指针,问你能不能只用常数的空间快速判断一个链表是不是有环,如果有环,返回环的起始位置。

代码:

不能用额外的空间,所以必须通过遍历,判断有没有环的存在。

经典的判断方法(百度很多哦):

对于判断链表是否有环,方法很简单,用两个指针,一开始都指向头结点,一个是快指针,一次走两步,一个是慢指针,一次只走一步,当两个指针重合时表示存在环了。

根据此方法:

如图,a代代表链表起始位置到环开始位置的距离;x代表环起始位置到快慢指针节点相遇点的距离;c代表环的长度。

假设慢指针和快指针在9处第一次相遇,于是又慢指针走的距离 s_slow=a+x,

快指针会多走一圈之后来追上慢指针,于是走的距离应该是      s_fast=a+n*c+x(快指针可能走了n圈)

因为快指针的速度是慢指针的2倍,所以距离s_fast=2*s_slow.于是有:a+x+nc = 2*(a+x) =>nc = a + x => a = (n-1)c+c-x

当慢指针走距离a时候,快指针走了n-1圈加c-x的距离。

所以如果把慢指针放回起点S,让他重启走完a距离,快指针从相遇点9继续走,他们第二次肯定会相遇在4,也就是环的起点。

因为满指针走完a的时间里,快指针刚好走完了整数圈加c-x的距离,肯定会停在圈的起点。

技术分享

于是可以根据这个规律,求出环的起点:

java代码,不复杂,就是分别循环到两次,找到第二次相遇的点

    public ListNode detectCycle(ListNode head) {
        if(head==null){return null;}
        ListNode Slower = head;
        ListNode Faster = head;
        //循环到第一次相遇为止
        while(Faster!=null && Slower != null){
            Slower = Slower.next;
            Faster = Faster.next;
            if(Faster!=null){
                Faster = Faster.next;
            }
            else{
                return null;
            }
            System.out.println("Faster: "+Faster.val+"   "+"Slower: "+Slower.val);
            if(Slower==Faster){
                Slower = head;
                //循环到第二次相遇
                 while(Slower != Faster){
                     Slower = Slower.next;
                     Faster = Faster.next;
                     System.out.println("LittleCycle: Faster: "+Faster.val+"   "+"Slower: "+Slower.val);                  
                 }
                 return Slower;
            }
        }
        return null;    
    }

输出输出结果,构建如上图所示的环:

FirstCycle: Faster: 3   Slower: 2
FirstCycle: Faster: 5   Slower: 3
FirstCycle: Faster: 7   Slower: 4
FirstCycle: Faster: 9   Slower: 5
FirstCycle: Faster: 11   Slower: 6
FirstCycle: Faster: 5   Slower: 7
FirstCycle: Faster: 7   Slower: 8
FirstCycle: Faster: 9   Slower: 9
SecondCycle: Faster: 10   Slower: 2
SecondCycle: Faster: 11   Slower: 3
SecondCycle: Faster: 4   Slower: 4
环的起点: 4

问题代码逻辑不复复杂,但是解题思路很关键,也是百度学习了很久,当然测试也需要构建存在环的链表这种数据结构。

简单写下我的链表创建方法,也是凑了好久凑出来的,还在寻找好的方案:

先递归创建一个链表,然后把最后一个对象指向其中的一个(cycle=4),构建成环:)

本想直接递归创建一个带环的列表,但是很难在ListNode类中实现(至少我还没想出来:(),先这样用吧:

public class ListNode {
     int val;
     ListNode next;
     ListNode(int x) {
     val = x;
     next = null;
     }

     //递归调用makeListNode,创建列表。
     ListNode head;
     public ListNode(int[] array){
         head=makeListNode(array,0);
     } 

     //根据对象的值获取链表中某个对象        
     public ListNode getNode(int value){
         ListNode temp = this.head;
         while(temp.val != value){
              temp = temp.next;
         }
         return temp;
     }

        /**
         * 采用递归的方式创建链表
         * 传入的是链表的数组表示法
         * 构造后是链表的链表表示法
         */
        public static ListNode makeListNode(int[] array,int index){
            if(index < array.length){
                int value=http://www.mamicode.com/array[index];
                ListNode t=new ListNode(value);                
                t.next=makeListNode(array,++index);
                return t;
            }
            return null;
        }
}

 

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Solution a = new Solution();      
        int[] arr = {1,2,3,4,5,6,7,8,9,10,11};
        int cycle = 4;        
        ListNode list = new ListNode(arr);

   //把链表最后一位指向链表中第cycle个对象
        if(cycle>0){
            for (int i = 0;i<arr.length;i++){
                 if(cycle==arr[i]){
                     list.getNode(arr[arr.length-1]).next = list.getNode(cycle);
                 }
            }
        }        
        
        ListNode x = a.detectCycle(list.head);
        if(x==null){
            System.out.println("yes");
        }
        else{
            System.out.println(x.val);    
        }

最后,提交结果:

技术分享

142. Linked List Cycle II