链表——环形链表

题目

首先，来列一下环形链表的特征：

至少存在一个节点，且有两个指针指向这个节点
链表中有且只有一个环，且这个环一定不能在中间（这里解释一下，如果环在中间，则一定存在有一个节点有两个指出去的指针，显然这是不存在的）
遍历环形链表至少会访问同一个节点两次，且会形成循环无法终止

然后我是立马想到了用set集合的特性来做，不断地把遍历到的节点放入set集合中，同时检查insert操作的返回值，如果发现插入了同一个节点两次，则说明有环

class Solution {
public:
    bool hasCycle(ListNode *head) {
        set<ListNode*> nodes;
        while (head) {
            auto temp = nodes.insert(head);
            if (temp.second == false) return true;
            head = head->next;
        }
        return false;
    }
};

insert操作的返回值类型，其"second"属性是个bool值标志是否重复插入

这个方法大家都能想到，效率确实不高，还需要额外空间，所以有了下面两种比较好的方法

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head == NULL || head->next == NULL) return false;
        ListNode *p1 = head;
        ListNode *p2 = head->next;
        while(p1 && p2 && p1->next && p2->next && p2->next->next){
            p1 = p1->next;
            p2 = p2->next->next;
            if(p1 == p2){
                return true;
            }
        }
        
        return p1 == p2;  // 这里其实也可以return false，结果一样
    }
};

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == nullptr || head->next == nullptr) {
            return false;
        }
        ListNode *p = head;
        ListNode *q = head->next;
        while (q && q != p && q->next != nullptr) {
            p = p->next;
            q = q->next->next;
        }
        if (q == p) {
            return true;
        }
        return false;
    }
};

其实这两种方法的算法思想是一样的，设置两个指针，开始时一个指针指向头节点，暂叫作慢指针，另一个指针指向其后一个节点，暂叫作快指针。快指针每次向后移动两个节点，慢指针则是每次移动一个节点，然后用这两个指针进行链表的遍历，只要发现两个节点在移动后相遇，则说明存在环。
其实也很好理解，就像两个人在环形操场上跑步，只要两个人速度不一样，那么总有一个时刻两人相遇。
但是问题来了，快指针每次移动两个位置，慢指针每次移动一个位置，假如快指针在移动的时候正好越过了慢指针怎么办？其实很简单，如果想发生这种情况，只有一个条件，那就是存在一个移动结束时刻，慢指针和快指针相遇，这显然是函数终止条件。

唯一发生快指针越过慢指针而不相遇的情况

最后编辑于：2018.07.27 20:43:20