Leetcode.141.Linked List Cycle

题目

给定一个单向链表, 判断该链表是否形成循环.

Input: head = [3,2,0,-4], pos = 1
Output: true
Input: head = [1,2], pos = 0
Output: true
Input: head = [1], pos = -1
Output: false

思路1

set判断. 遍历链表, 使用一个set将链表值存储起来, 如果遇到set里已有的值即为循环链表.

bool hasCycle2(ListNode *head) {
    set<ListNode*> s;
    set<ListNode*>::iterator iter;
    while(head != nullptr) {
        iter = s.find(head);
        if (iter != s.end()) {
            return true;
        } else {
            s.insert(head);
        }

        head = head->next;
    }

    return false;
}

思路2

双指针. 一个快指针, 每次走两步. 一个慢指针, 每次走一步. 当快指针和慢指针都到结尾前相遇, 即为循环指针.

bool hasCycle(ListNode *head) {
    if (head == nullptr || head->next == nullptr) return false;
    ListNode *slow = head;
    ListNode *fast = head->next;

    while(fast != slow) {
        if (fast == nullptr || fast->next == nullptr) {
            return false;
        }
        fast = fast->next->next;
        slow = slow->next;
    }

    return true;
}

总结

空指针问题需要慎重, 每次使用->都要检查好.
双指针需要灵活运用, 不止左右指针, 还有快慢指针.