2-环形链表

自己的做法

算法思想

使用C++的vector数据结构存储已访问过的结点，从链表头节点开始，首先在vector中查找是否已存在该结点，存在表示已经访问过该结点，代表链表有环；不存在则把该结点放入vector中，head指向下一个结点。

只有两种情况：

• 不是环形链表，则链表最后一个结点的next指向NULL
• 是环形链表，则一定会出现vector存在当前节点的情况

以此来设置循环结束的时机。

即当前结点存在于vector中或当前结点为NULL。

算法实现

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

class Solution {
public:
    bool hasCycle(ListNode *head) {

        if(head == nullptr || head->next == nullptr) {
            return false;
        }

        vector<ListNode *> addresses;
        ListNode *current = head;
        bool flag = false;
        while(current != nullptr && !flag) {
            vector<ListNode *>::iterator result;
            result = find(addresses.begin(), addresses.end(), current);
            if(result != addresses.end()) {
                    flag = true;
                	breaks;
            } else {
                addresses.push_back(current);
                current = current->next;
            }
        }
        return flag;
    }
};

性能分析

需要遍历整个链表，所以时间复杂度为$O({n})$，空间复杂度也为$O(n)$。

更好的做法

哈希表

算法思想

和我自己的做法意思不大差，但是官方提供的代码使用的数据结构更好，代码更简洁。

即：

遍历所有节点，每次遍历到一个节点，判断该结点是否被访问过。

使用哈希表来存储所有已经访问过的节点。

使用set集合。

即Java中set类，或C++中unordered_set类。

算法实现

class Solution {
public:
    static bool hasCycle(ListNode *head) {

        unordered_set<ListNode *> seen;
        
        bool flag = false;

        while (head != nullptr) {
            if(seen.count(head)) {
                flag = true;
                break;
            } else {
                seen.insert(head);
                head = head->next;
            }
        }
        return flag;
    }
};

性能分析

同样，时间复杂度为$O({n})$，空间复杂度也为$O(n)$。

快慢指针

算法思想

该方法需要对Floyd判圈算法(又称龟兔赛跑算法)有所了解。

假想 乌龟 和 兔子 在链表上移动，兔子跑得快，乌龟跑得慢。那么当乌龟和兔子在链表上同一个节点开始移动时，如果链表没有环，那么兔子将一直在乌龟前方，直到乌龟到达最后一个节点；如果链表有环，那么兔子会先于乌龟进入环，并一直在环内移动。等到乌龟进入环后，由于兔子的速度快，他一定(注意，是一定会相遇)会在某个时刻和乌龟相遇。

可以根据上述思路来解决该题。定义两个指针，一快一慢。慢指针每次只移动一步，快指针每次移动两步。初始状态，慢指针在位置head，快指针在位置head->next，这样当快指针在某一时刻追上慢指针，就说明链表为环形指针；当快指针为null或快指针的next为null，就说明链表不为环形链表。

注：

• 为什么要判断快指针和快指针的next：因为快指针每次走两步，所以如果链表节点个数为奇数个，那么快指针走n次，会正好走到最后一个节点的后面，即null；当链表节点个数为偶数个，那么走n次，快指针正好指向最后一个节点。因此两个情况有任意一种情况出现，即出现null，则代表不是环形链表。
• 为什么初始状态慢指针在head位置，快指针在head->next位置：这是因为使用while循环，判断循环结束条件为slow != fast，即快指针和慢指针不相等，若快慢指针初始都在head位置，那就不会进入循环。当然也可以使用do while循环。那样，快慢指针都可以放在head位置。
• 其实快指针也可以一次走多步，3步，4步。都行， 但是这样会增加算法复杂度。

算法实现

class Solution {
public:
    bool hasCycle(ListNode *head) {

        if(head == nullptr || head->next == nullptr) {
            return false;
        }

        ListNode * slow = head;
        ListNode * fast = head->next;

        while (slow != fast) {
            if(fast == nullptr || fast->next == nullptr) {
                return false;
            }
            slow = slow->next;
            fast = fast->next->next;
        }
        return true;
    }
};

性能分析

• 时间复杂度：$O(n)$，其中n是链表节点数。

• 空间复杂度：$O(1)$，只使用了两个指针额外空间。