判断链表是否有环

快慢指针: 每循环一次两指针距离+1，相遇时两指针相差距离nb，b=环的长度。
l = 2s
l - s = nb
s = nb
sum = a + nb = a + s

  • 时间复杂度 O(n)
  • 空间复杂度 O(1)
    1. class Solution {
    2. public:
    3.   bool hasCycle(ListNode *head) {
    4.       ListNode *slow = head;
    5.       ListNode *fast = head;
    6.       while (fast && fast->next) {  // fast不能走一步和两步的情况
    7.           slow = slow->next;
    8.           fast = fast->next->next;
    9.           if (slow == fast) return true;
    10.       }
    11.       return false;
    12.   }
    13. };

链表中环的入口结点

#include <iostream>
#include <vector>
using namespace std;

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int n) : val(n), next(nullptr) {};
};

ListNode *solution(ListNode *p_head) {
    if (p_head == nullptr) return nullptr;
    ListNode *slow = p_head;
    ListNode *fast = p_head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        // 快慢指针：每循环一次两个指针距离+1，相遇时两个指针走的距离相差nb
        // 此时 假设慢指针走了s，快指针走了f，那么可以得到
        // f = 2s, f-s = nb
        // 所以s = nb 慢指针走的距离是环长度的n倍
        // l = a + nb = a + s
        // 要到达环入口结点要走的距离是a+nb，再往前走a的距离就可以到达入口结点
        // 所以让快指针回到头结点与慢指针同时往前走，当相遇时两者都走了a的距离，此时为环的入口结点
        if (fast == slow) {
            fast = p_head;
            while (fast != slow) {
                fast = fast->next;
                slow = slow->next;
            }
            return fast;
        }
    }
    return nullptr;
}

int main() {
    ListNode *p0 = new ListNode(0);
    ListNode *p1 = new ListNode(1);
    ListNode *p2 = new ListNode(2);
    ListNode *p3 = new ListNode(3);
    ListNode *p4 = new ListNode(4);

    p0->next = p1;
    p1->next = p2;
    p2->next = p3;
    p3->next = p4;
    p4->next = p2;

    ListNode *p_res = solution(p0);
    cout << p_res->val << endl;

    return 0;
}