Double pointer to evaluate whether meeting


  • 0
    K
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        bool hasCycle(ListNode *head) {
         if (head == NULL)
    		return false;
            if (head->next == NULL)
    		return false;
    	if (head->next == head)
    		return true;
    
    	ListNode *pSlow = head;
    	ListNode *pFast = head;
    
    	pSlow = pSlow->next;
    	pFast = pFast->next->next;
    
    	while (pSlow != pFast)
    	{
    		pSlow = pSlow->next;
    		if (pSlow == NULL || pFast == NULL)
    		{
    			return false;
    		}
    		if (pFast->next == NULL)
    		{
    			return false;
    		}
    		else
    		{
    			pFast = pFast->next;
    			if (pFast->next == NULL)
    			{
    				return false;
    			}
    			else
    			{
    				pFast = pFast->next;
    			}
    		}
    	}
    
    	if (pSlow == NULL)
    	{
    		return false;
    	}
    	else
    	{
    		return true;
    	}
        }
    };
    

    算法思想:用两个指针,一个指针走一步,另一个指针每次走两步,若遇到则说明有环,否则遇到了NULL,则说明没有环。

    insight : double pointer, one walks one step, the other walks two step, if they meet, then it exit cycle. Otherwise it does not exit cycle.


Log in to reply
 

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