【题解】leetcode-141环形链表

题目描述

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。

解题思路

查看一个链表中是否有环的经典解题思路就是使用快慢指针（双指针），即一个慢指针和快指针同时从头节点出发，如果链表中有环，则两指针在之后一定会相遇，否则，不相遇。其中，慢指针的步长为1，而快指针的步长为2。

• 证明
  如图所示，假设链表中某节点a到节点b有环，节点a到节点b之间有m个节点。
  

  image
  令慢指针p1（步长为1），快指针p2（步长为2），同时从头节点出发，假设在p1走了K步之后和p2在环内某节点处相遇，则：
  2 * p1走的步数 = p2走的步数，即 2K=K+a(m+2)，解得K=a*(m+2)。

  显然，当m取任何自然数时，都能取到K值，即这个式子是可解的。
  当链表中没有环时，显然快指针会先于慢指针到达链表尾，两个指针不会再相遇。
  因此，当快慢指针再次相遇时，说明链表中存在环。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == NULL || head->next == NULL)
            return false;
        ListNode* p1 = head;
        ListNode* p2 = head->next->next;

        while (p1 != p2 && p1 != NULL && p2 != NULL && p2->next != NULL){
            p1 = p1->next;
            p2 = p2->next->next;
        }
        return p1 == p2 && p1 != NULL && p2 != NULL && p2->next != NULL;
    }
};