Thursday, April 9, 2015

LeetCode OJ - Linked List Cycle

Problem:

Please find the problem here.

Solution:

This problem is pretty standard with a standard solution. It would be hard to find if one don't know this solution beforehand, but it is otherwise pretty simple.

We maintain two pointers, one slow pointer that move 1 step at a time, and a fast pointer that move twice as fast. Suppose fast pointer equals the slow pointer, it must have wrapped around and we conclude there is indeed a cycle. If the fast pointer reach NULL, we conclude the list has an end and therefore there is no cycle.

The only question remain is, is it possible for the fast pointer never exactly equals slow pointer and infinitely looping there, the answer is negative. Let the length of the cycle be $ a $, some initial position $ b $ for the slow pointer and initial position $ c $ for the fast pointer when $ t = 0 $, so we effectively saying $ t $ started when both pointers enter the cycle, $ b $ and $ c $ measured from an arbitrary starting point in the cycle.

Now at time $ t $, we have position of the slow pointer equals to $ mod(b + t, a) $, and the position of the fast pointer equals to $ mod(c + 2t, a) $, so we know when $ t = b - c $, they have to be equal.

Beware of the empty list.

Code:


#include "stdafx.h"

// https://leetcode.com/problems/linked-list-cycle/

#include "LEET_LINKED_LIST_CYCLE.h"
#include <map>
#include <iostream>
#include <vector>

using namespace std;

namespace _LEET_LINKED_LIST_CYCLE
{
    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;
            }

            ListNode* fast = head;
            ListNode* slow = head;
            while (true)
            {
                fast = fast->next;
                if (fast == NULL)
                {
                    return false;
                }
                fast = fast->next;
                if (fast == NULL)
                {
                    return false;
                }
                slow = slow->next;
                if (fast == slow)
                {
                    return true;
                }
            }
        }
    };
};

using namespace _LEET_LINKED_LIST_CYCLE;

int LEET_LINKED_LIST_CYCLE()
{
    ListNode a(0);
    ListNode b(1);
    ListNode c(2);
    ListNode d(3);
    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &a;
    Solution solution;
    cout << (solution.hasCycle(&a) ? "Yes" : "No") << endl;
    return 0;
}

No comments :

Post a Comment