這一題也算是簡單的題目，但是可以延伸出不少follow-up questions。

一個簡單的想法是，要判斷有沒有cycle，在走過每個ListNode的時候都把他塞入hashmap，之後只要走到某一個node，這個node的next已經存在於hashmap中，就表示有cycle。

可以實測的C++ code如下:

#include <iostream>
#include <map>

using namespace std;

struct ListNode {
     int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

    //if head == NULL or head->next == NULL return false;
    //walk through all node in the linked list
    //    if node->next is not in the hashmap
    //        store the node in the hashmap
    //        go to the next node
    //    if node->next is in the hashmap
    //        return true
    //
    //    return false

    bool hasCycle(ListNode *head) {
        if(head == NULL || head->next == NULL)
            return false;

        map<ListNode*, int> m;

        ListNode* cur = head;    
        while (cur != NULL)
        {
            if(m.find(cur->next) != m.end())
                return true;
            else
            {
                m[cur]=1;
                cur = cur->next;
            }
        }

        return false;
    }

int main() {
    ListNode a(1);
    ListNode b(2);
    ListNode c(3);
    ListNode d(4);

    ListNode* head = &a;
    ListNode* b_ptr = &b;
    ListNode* c_ptr = &c;
    ListNode* d_ptr = &d;

    head->next = b_ptr;
    b_ptr->next = c_ptr;
    c_ptr->next = d_ptr;
    d_ptr->next = NULL;

    map<ListNode*, int> m;

    m[head]=1;

    if(hasCycle(head))
        cout << "True\n";

    return 0;
}

但是這樣實作出來的code跑超慢，一個小小的優化是用unordered_map，因為unordered_map的insert和find的時間複雜度比ordered_map低。

Follow up的問題是，能不能不用額外的空間就判斷有沒有cycle。這邊直接參考別人很聰明的作法，設置兩個pointer - walker 跟 runner。walker一次走一步、runner一次走兩步，如果有cycle，兩者遲早會相遇，否則runner會先走到NULL。另外在while迴圈的條件中，需要先檢查runner可不可以一次走兩步。

程式碼如下:

//  Floyd's cycle-finding algorithm, aka tortoise and hare algorithm. The idea is to have two references to the list and move them at different speeds. Move one forward by 1 node and the other by 2 nodes. If the linked list has a loop they will definitely meet.
//  Since the runner's speed is faster than walker, then it is guaranteed that runner will pass walker in some time. The only thing we need to prove is that the runner never jumps over walker so never meet. Suppose the runner jumps over walker in one unit of time, then we need to guarantee that 2 > distance + 1. So distance < 1 so distance = 0. This implies that runner already meets walker, contradiction. So runner will never jumps over walker. Runner will pass walker + runner never jumps over => runner will meet walker.
//  A common logic mistake: If there is no tail, then no node has next pointer pointing to NULL, then the program never ends. But here the logic is that if a cycle exists, there will be no tail, and eventually it will jump out of the loop; if not, there will be a tail and the condition in While() still valid.

class Solution {
public:    
    bool hasCycle(ListNode *head) {
        if(head == NULL || head->next == NULL)
            return false;

        ListNode* walker = head;
        ListNode* runner = head;
        while(runner->next!=NULL && runner->next->next!=NULL) {
            walker = walker->next;
            runner = runner->next->next;

            if(walker==runner) 
                return true;
        }

        return false;
    }
};

再探討一下，如果把while的條件變寬鬆，變成 while( runner->next->next!=NULL) ，答案會錯，為什麼呢? 讓我們想一個例子，1->2->3->4->5->NULL，走了兩回合之後，walker會指到3，runner會指到5，進入下一次while條件判斷的時候，程式會想要去取5->next->next，可是5->next就已經是NULL了，NULL->next是一個不存在的東西，所以程式會出錯。這也是為什麼要先檢查 runner->next!=NULL 再檢查 runner->next->next!=NULL。

Java版本：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        //declare a set to save all visited nodes
        //visit each node in the linked list, 
        //  if node's next is already in the set, return true
        //  else, add node to set, node = node.next.
        //base case?
        if(head == null) return false;
        Set<ListNode> set = new HashSet<ListNode>();
        ListNode node = head;
        while(node!=null){
            if(set.contains(node.next))
                return true;
            set.add(node);
            node = node.next;
        }
        return false;
    }
}