题目主要信息:

  • 给定一个链表的头节点,判断这个链表是否有环
  • 环形链表如下所示: alt

具体思路:

我们都知道链表不像二叉树,每个节点只有一个val值和一个next指针,也就是说一个节点只能有一个指针指向下一个节点,不能有两个指针,那这时我们就可以说一个性质:环形链表的环一定在末尾,末尾没有NULL了。为什么这样说呢?仔细看上图,在环2,0,-4中,没有任何一个节点可以指针指出环,它们只能在环内不断循环,因此环后面不可能还有一条尾巴。如果是普通线形链表末尾一定有NULL,那我们可以根据链表中是否有NULL判断是不是有环。

但是,环形链表遍历过程中会不断循环,线形链表遍历到NULL结束了,但是环形链表何时能结束呢?我们可以用一种双指针技巧,这也是处理环形链表常用的技巧:

  • step 1:设置快慢两个指针,初始都指向链表头。
  • step 2:遍历链表,快指针每次走两步,慢指针每次走一步。
  • step 3:如果快指针到了链表末尾,说明没有环,因为它每次走两步,所以要验证连续两步是否为NULL。
  • step 4:如果链表有环,那快慢双指针会在环内循环,因为快指针每次走两步,因此快指针会在环内追到慢指针,二者相遇就代表有环。

双指针过程可以参考如下图示:

alt

代码实现:

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head == NULL) //先判断链表为空的情况
            return false;
        ListNode* fast = head; //快慢双指针
        ListNode* slow = head;
        while(fast != NULL && fast->next != NULL){ //如果没环快指针会先到链表尾
            fast = fast->next->next; //快指针移动两步
            slow = slow->next; //慢指针移动一步
            if(fast == slow) //相遇则有环
                return true;
        }
        return false; //到末尾则没有环
    }
};

复杂度分析:

  • 时间复杂度:O(n)O(n),最坏情况下遍历链表nn个节点
  • 空间复杂度:O(1)O(1),仅使用了两个指针,没有额外辅助空间