My O(n) solution without using extra space:cut the ring into two "rail"


  • 2
    K

    Hey! I've found a solution with O(n) time complexity and O(1) space complexity. My method is very simple with the follow steps:

    1. Find a ring point via "fast and slow running" method.if there isn't a node like that,then return NULL;
    2. Cut the ring at the ring point found before,making the cycle link list like two rails with different start points jioning together.
    3. Make the two "rails" the same length.
    4. search the two "rails" the same time,and compare the two nodes,if they are equal,return one which is the answer .

    my code:

    	ListNode *detectCycle(ListNode *head) {
    	ListNode * p1,* p2,* p3;
    	int m = 0;
    	if(!head||!head->next)
    		return NULL;
    	p1 = head->next;
    	p2 = head->next->next;
    	while(true)      //find a ring node using "fast and slow" method
    	{
    		if(p1 == p2)     //if find the ring node,cut the ring at this node.
    		{                // It like two rails with different start point jioning together.
    			p2 = p1->next;  //make p2 the front node of the cut node,in other word the second rail's start point.
    							//head is the first rail's start point.
    			p1->next = NULL; //make the cute node's next NULL.
    			p1 = head;
    			p3 = p1;
    			while(p3)        //this code's purpose is to make the two rails  the same length.
    			{
    				p3 = p3->next;
    				m++;
    			}
    			p3 = p2;
    			while(p3)
    			{
    				p3 = p3->next;
    				m--;
    			}
    			if(m>=0)
    				while(m--)
    					p1 = p1->next;
    			else
    				while(m++)
    					p2 = p2->next;
    
    			while(p1&&p2)		//search the two rails in the same time;
    			{
    				if(p1 == p2)   //the first equal node is the begin node of the cycle
    					return p1; //return the node.
    				p1 = p1->next;
    				p2 = p2->next;
    			}
    		}
    		if(p1->next)
    			p1 = p1->next;
    		else
    			return NULL;
    		if(p2->next&&p2->next->next)
    			p2 = p2->next->next;
    		else
    			return NULL;
    	}
    	return NULL;
    }

  • 0
    T

    The idea is good, but does this method change the original list? Sometimes we are not allowed to change the original one.
    However, if we are allowed to change it, there will be many O(1) space complexity algorithms such as changing the 'val'.


  • 0
    K

    Actually,we don't need to change the original list.The key point of this method is to find a ring node, and then search concurrently from this ring node and the start node of the list. If there is a ring, they will meet at the start node of the ring.


  • 3
    C

    Hi, the idea of 'fast and slow' is cool!! I use your idea and simplify the code. First the 'fast and slow' method is used to find the size of the cycle (its multiples but it doesn't matter). Then search from the head again using two pointer which distance is the size. The first node they meet is the start point of the cycle. If there is no cycle, it will occur exception, so I return none at catch block.

    Here is my code.

    class Solution:
    # @param head, a ListNode
    # @return a list node
    def detectCycle(self, head):
        try:
            # Find the size of the cycle
            ptr1, ptr2 = head, head.next
            size = 1
            while ptr1 != ptr2:
                ptr1 = ptr1.next
                ptr2 = ptr2.next.next
                size += 1
            
            # Let ptr2 is size step front of ptr1
            ptr1, ptr2 = head, head
            for i in range(size):
                ptr2 = ptr2.next
            
            # Move two pointer at the same speed,
            # and they will meet at the start of the ring.
            while ptr1 != ptr2:
                ptr1 = ptr1.next
                ptr2 = ptr2.next
            return ptr1
            
        except:
            # If there is no cycle, then 'NoneType' exception occurs.
            return None

  • 0
    B

    wow! I got the exact same solution with you! Your description is really expressive.

    Here is my Java edition:

    public class Solution {
        public ListNode detectCycle(ListNode head) {
        	ListNode fastNode = head;
            ListNode slowNode = head;
            while(fastNode != null && slowNode != null){
            	slowNode = slowNode.next;
            	fastNode = fastNode.next;
            	if(fastNode == null)
            		return null;
            	fastNode = fastNode.next;
            	
            	if(fastNode == slowNode && fastNode != null){
            		/** 
            		 * yes, we got the circle. Let's find the node where the cycle
            		 * begins. 
            		 */
            		return findBeginningCycleNode(head, fastNode);
            	}
            }
            return null;
        }
    
    	private ListNode findBeginningCycleNode(ListNode head1, ListNode nodeInCycle) {
    		ListNode head2   =  nodeInCycle.next;
    		nodeInCycle.next =  null; // break the cycle
    		return firstCommonNode(head1, head2);
    	}
    
    	private ListNode firstCommonNode(ListNode head1, ListNode head2) {
    		int len1 = getLength(head1);
    		int len2 = getLength(head2);
    		
    		if(len1 > len2)
    			for(int i = 0; i < len1 - len2; i++)
    				head1 = head1.next;
    		else
    			for(int i = 0; i < len2 - len1; i++)
    				head2 = head2.next;
    		
    		while(true){
    			if(head1 == head2)
    				return head1;
    			head1 = head1.next;
    			head2 = head2.next;
    		}
    	}
    
    	private int getLength(ListNode head) {
    		int count = 1;
    		while((head = head.next) != null)
    			count++;
    		return count;
    	}
    
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.