C++实现LeetCode(141.单链表中的环)

下面我就为您详细讲解“C++实现LeetCode(141.单链表中的环)”的完整攻略。

问题描述

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

若链表中有环，则返回true，否则返回false。

示例输入与输出：

示例1:

输入: head = [3,2,0,-4], pos = 1

输出: true

解释: 链表中有一个环，其尾部连接到第二个节点。

示例 2:

输入: head = [1,2], pos = 0

输出: true

解释: 链表中有一个环，其尾部连接到第一个节点。

思路解析

我们可以利用快慢指针的方法解决这个问题。

假设我们有两个指针，名为fast和slow。我们可以让slow每一次走一步，让fast每一次走两步。因为如果链表中存在环的话，fast一定会比slow先到达环中，然后二者在环中相遇。如果fast在走的过程中到达了链表的尾部，就表明链表中不存在环，此时我们可以返回false。

在代码中，我们可以利用两个指针来实现上述思路，具体步骤如下：

1.首先定义两个指针slow和fast，初始值都为链表的头节点head。

2.进入循环，循环结束的条件是fast或者fast的下一个节点为空。这个判断条件就是fast指针每次走动的时候都要判断是否为空。

3.每一次循环，slow走一步，fast走两步。如果fast为空或者fast的下一个节点为空，就直接返回false。

4.否则，如果fast和slow相遇了，就说明链表中存在环，返回true。

最后的代码如下所示：

bool hasCycle(ListNode *head) {
    if(head == NULL || head->next == NULL){
        return false;
    }
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast != NULL && fast->next != NULL){
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast){
            return true;
        }
    }
    return false;
}

示例说明

下面我们将通过两个示例来说明刚才所讲的算法是如何工作的。

示例1：

输入: head = [3,2,0,-4], pos = 1

输出: true

解释: 链表中有一个环，其尾部连接到第二个节点。

我们可以根据输入来构造一个链表，如下所示：

3 -> 2 -> 0 -> -4

↑          ↓
- - - - - -

通过使用刚才所讲的算法，slow和fast的值会在节点2处相遇，因此算法返回true。

示例2：

输入: head = [1,2], pos = 0

输出: true

解释: 链表中有一个环，其尾部连接到第一个节点。

我们可以根据输入来构造一个链表，如下所示：

1 -> 2

↑ ↓

---

通过使用刚才所讲的算法，slow和fast的值会在节点1处相遇，因此算法返回true。

总结

使用快慢指针是解决链表环问题的一种简单有效的解法。我们可以将其中的思路应用到其他类似的问题中。在实际的应用中，我们不仅要掌握这个算法的原理，还要注意边界条件的判断和代码优化。