online advertising

Friday, March 18, 2016

LeetCode OJ - Linked List Cycle II

Problem: 

Please find the problem here.

Analysis:

In the last problem, we already solved the problem to detect whether or not there is a cycle using a slow pointer and a fast pointer. We get a point in the cycle, but that may not be the starting point of the cycle.

The key observation here is if we have a complete cycle instead, and we start from a point inside the cycle, it always meet at the same starting point.

Let's say we have a cycle like 1 -> 2 -> 3 -> 4 -> 5 -> 1, and the both pointers start from 1, we have the pointer sequence

1, 1
2, 3
3, 5
4, 2
5, 4
1, 1

The logic here is simple, the fast pointer make two cycles when the slow pointer make one.

Solution:

Now here is the interesting thing, for an arbitrary list with cycle, we already know a point on the cycle, the meeting point, what if we trace back the path?

Let say, we have the list 1 -> 2 -> 3 -> 4 - >5 -> 6 -> 3, so the forward pointer sequence would be

1, 1
2, 3
3, 5
4, 3
5, 5

Of course, the backward sequence would simply be reading the sequence above backward, at some point, the pointers would leave the cycle. With the observation above, we know, if we make the pointers to stay on the cycle (instead of going back to 1), it will eventually go back to the meeting point. Let us illustrate the reversed path here

Original (Changed)
5, 5
4, 3
3, 5
2(3), 3(3)
1(5), 1(5)

Notice in the illustration above, what is more true, is that it takes the same amount of time to get back to the original meeting point. This is always true because one can think of projecting the initial portion of the path back to the cycle, they started at the same place and therefore the same must be identical.

With that, we can come up with this simple algorithm.

Code:

#include "stdafx.h"

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

#include "LEET_LINKED_LIST_CYCLE_II.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_LINKED_LIST_CYCLE_II
{
    struct ListNode
    {
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };
    class Solution
    {
    public:
        ListNode* detectCycle(ListNode *head)
        {
            if (head == NULL)
            {
                return NULL;
            }

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

using namespace _LEET_LINKED_LIST_CYCLE_II;

int LEET_LINKED_LIST_CYCLE_II()
{
    Solution solution;
    ListNode a(0);
    ListNode b(1);
    ListNode c(2);
    ListNode d(3);
    ListNode e(4);
    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &e;
    e.next = &b;
    cout << (solution.detectCycle(&a) == &b) << endl;
    return 0;
}

No comments :

Post a Comment