141.环形链表[easy]

2019-05-05 阅读量

LeetCode 算法题停止更新，请移步至 GitHub。

题目地址

141. 环形链表

题目描述

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

解题方法

1.哈希表

使用哈希表来存储节点，key 为当前节点，value 为当前节点的下一节点，存储形式为 [node : node -> next]
访问当前节点时，先在字典中取出当前节点对应的 value，也就是取出当前节点的下一节点，如果下一节点在字典中的 key 存在，则说明当前节点的下一节点为链表中的某一个节点，即链表有环。如果下一节点在 key 中不存在，则说明链表没有环。

/**
 * 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) {
        if (head == NULL || head -> next == NULL) {
            return false;
        }
        
        unordered_map<ListNode *, ListNode *> map;
        
        while (head) {
            // map 中存储的是 [head : head -> next]
            map[head] = head -> next;
            
            // map[head] 取出的是 head -> next；如果 head -> next 存在字典的 key 中，则说明有环。
            if (map.find(map[head]) != map.end()) return true;
            
            head = head -> next;
        }
        return false;
    }
};

执行用时 : 32 ms, 在Linked List Cycle的C++提交中击败了23.23% 的用户

内存消耗 : 12.5 MB, 在Linked List Cycle的C++提交中击败了5.02% 的用户

时间复杂度：O(n)

空间复杂度：O(n)

2.双指针法

通过使用具有不同速度的快、慢两个指针遍历链表，空间复杂度可以被降低至 O(1)O(1)。慢指针每次移动一步，而快指针每次移动两步。

如果列表中不存在环，最终快指针将会最先到达尾部，此时我们可以返回 false。

现在考虑一个环形链表，把慢指针和快指针想象成两个在环形赛道上跑步的运动员（分别称之为慢跑者与快跑者）。而快跑者最终一定会追上慢跑者。这是为什么呢？考虑下面这种情况（记作情况 A） - 假如快跑者只落后慢跑者一步，在下一次迭代中，它们就会分别跑了一步或两步并相遇。

其他情况又会怎样呢？例如，我们没有考虑快跑者在慢跑者之后两步或三步的情况。但其实不难想到，因为在下一次或者下下次迭代后，又会变成上面提到的情况 A。

/**
 * 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) {
        if (head == NULL || head -> next == NULL) {
            return false;
        }
        ListNode *slow = head;
        ListNode *fast = head -> next;
        while (slow != fast) {
            if (fast == NULL || fast -> next == NULL) {
                return false;
            }
            slow = slow -> next;
            fast = fast -> next -> next;
        }
        return true;
    }
};

执行用时 : 24 ms, 在Linked List Cycle的C++提交中击败了50.14% 的用户

内存消耗 : 9.7 MB, 在Linked List Cycle的C++提交中击败了55.64% 的用户

时间复杂度：O(n)

空间复杂度：O(1)