题目考查的知识点

  • 本题抽象为链表是否存在环的问题。
  • 同时考察快慢指针。

题目解答方法的文字解析

    如果将尾结点的 next 指针指向其他任意一个结点，那么链表就存在了一个环。

  1. 当一个链表有环时，快慢指针都会陷入环中进行无限次移动，然后变成了追及问题。
  2. 想象一下在操场跑步的场景（有环），只要一直跑下去，快的总会追上慢的。
  3. 当两个指针都进入环后，每轮移动使得慢指针到快指针的距离增加一，同时快指针到慢指针的距离也减少一，只要一直移动下去，快指针总会追上慢指针。

本题解析所用的编程语言

  • c++

完整且正确的编程代码

class Solution {
  public:
    bool hasCycle(ListNode* head) {
	  	// 初始化快慢指针都为头节点
        ListNode* slow = head, * fast = head;
	  	// 只要快慢指针还可以继续前进
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;// 慢指针每次前进一个节点
            fast = fast->next->next;// 快指针每次前进两个节点
		  	//（while里面的条件保证了不会有空指针的访问）
            if (fast && slow->val == fast->val)//快慢指针相遇
                return true;
        }

        return false;
    }
};
/*
2023.08.03
*/