当前位置：首页 > article >正文

快慢指针：链表问题的利器

article 2025/1/18 22:23:22

快慢指针：链表问题的利器

1. 快慢指针的基本概念

快慢指针是一种双指针技巧，通常用于解决链表问题。它使用两个指针，一个指针（慢指针）每次移动一步，另一个指针（快指针）每次移动两步。通过这种移动方式，快指针的移动速度是慢指针的两倍，因此快指针会先到达链表的末尾。

2. 快慢指针的使用场景

2.1 寻找链表的中间节点

这是快慢指针最常见的应用场景之一。通过快慢指针，可以轻松找到链表的中间节点。当快指针到达链表末尾时，慢指针正好位于链表的中间位置。

示例代码：

ListNode *middleNode(ListNode *head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }

    ListNode *fast = head, *slow = head;
    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    if (fast->next != NULL) {
        slow = slow->next;
    }

    return slow;
}

2.2 检测链表中的环

快慢指针也可以用于检测链表中是否存在环。如果链表中存在环，快指针和慢指针最终会在环内相遇。如果快指针到达链表末尾，则链表中不存在环。

示例代码：

bool hasCycle(ListNode *head) {
    if (head == NULL || head->next == NULL) {
        return false;
    }

    ListNode *fast = head, *slow = head;
    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            return true;
        }
    }

    return false;
}

2.3 寻找环的入口

如果链表中存在环，快慢指针还可以用于找到环的入口。当快指针和慢指针在环内相遇后，将其中一个指针重置为链表头，然后两个指针每次各移动一步，它们再次相遇的位置即为环的入口。

示例代码：

ListNode *detectCycle(ListNode *head) {
    if (head == NULL || head->next == NULL) {
        return NULL;
    }

    ListNode *fast = head, *slow = head;
    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            break;
        }
    }

    if (fast->next == NULL || fast->next->next == NULL) {
        return NULL;
    }

    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }

    return slow;
}

2.4 寻找链表的倒数第 k 个节点

快慢指针可以用于找到链表的倒数第 k 个节点。首先，将快指针向前移动 k 步，然后快慢指针同时移动，当快指针到达链表末尾时，慢指针正好位于倒数第 k 个节点。

示例代码：

ListNode *findKthToLast(ListNode *head, int k) {
    if (head == NULL) {
        return NULL;
    }

    ListNode *fast = head, *slow = head;
    for (int i = 0; i < k; i++) {
        if (fast == NULL) {
            return NULL;
        }
        fast = fast->next;
    }

    while (fast != NULL) {
        slow = slow->next;
        fast = fast->next;
    }

    return slow;
}