LeetCode - 141. Linked List Cycle

Category: Algorithm
Difficulty: Easy
Tags: Linked List, Two Pointers
Discription: https://leetcode.com/problems/linked-list-cycle/#/description

這題給我們一個鏈結串列，然後讓我們去判斷其中有沒有環狀之串列。
其中要注意的就是串列有可能長得像「9」，所以要好好規劃迴圈與分支判斷。

/**
 * 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) {
        ListNode *walker = head;
        ListNode *runner = head;
        while(runner && runner->next){
            runner = runner->next->next;
            walker = walker->next;
            if(walker == runner) return true;
        }
        return false;
    }
};

作法是使用兩個指標「walker」與「runner」，
前者在迴圈中逐步指向下一個元素，後者則是一次往後指兩個元素，
以此讓兩個指標在環狀鏈結串列中持續走訪，直至指向同一元素為止。
若迴圈中斷，便可以判斷此串列絕不是環狀鏈結串列。