算法-leetcode-141. 环形链表

题目链接 环形链表
方法1:hash表法,用hash记录访问过的节点,如果新访问的节点在hash表中,就说明有环
方法2:快慢指针法
1.快指针每次走两步,慢指针每次走一步
2.如果有环,则快指针会一直在环中转圈
3.慢指针到达环入口节点时,快慢指针变成一个追击问题,快指针速度比慢指针快1,必然能追上慢指针
代码如下:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    if (!head) {
        return false;
    }
    struct ListNode *fast, *slow;
    fast = head->next;
    slow = head;
    while (slow && fast) {
        if (fast == slow) {
            return true;
        }
        slow = slow->next;
        if (!fast->next) {
            return false;
        }
        fast = fast->next->next;
    }
    return false;
}

第一个版本的代码看上去比较杂乱,按照官方推荐的写法优化一下,清爽了很多

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

方法3:判断链表是否有指向null的元素,有就无环,没有就有环,因为之后最后一个元素才可能指向null
这种方法的问题是对于有环的情况,需要设置一个结束条件,可以通过限制循环结束条件来控制,在leetcode上限制1000次时是不可以的,10000次可以,

bool hasCycle(struct ListNode *head) {
    int count = 10000;
    while (count--) {
        if (!head) {
            return false;
        }
        head = head->next;
    }
    return true;
}
上一篇:leetcode--双指针6(141题/easy/java)


下一篇:【leetcode】-141-环形链表-判断是否有环