首页该链表有头指针head指向头结点，设计一个算法，查找链表倒数第k个元素.双指针法C++代码

该链表有头指针head指向头结点，设计一个算法，查找链表倒数第k个元素.双指针法C++代码

时间: 2025-02-15 07:03:47 浏览: 44

为了在链表中找到倒数第 k 个元素，你可以使用两个指针，通常称为快指针 (fast) 和慢指针 (slow)。快指针每次移动两步，慢指针每次移动一步，这样当快指针到达链表尾部时，慢指针正好停在倒数第二个位置。然后，快指针回退 k 步，此时慢指针的位置就是倒数第 k 个元素。以下是一个简单的 C++ 代码实现： ```cpp #include <iostream> // 定义链表节点结构体 struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(NULL) {} }; // 找到链表倒数第 k 个元素 ListNode* findKthToTail(ListNode* head, int k) { if (!head || !k) return nullptr; // 初始化快慢指针 ListNode* fast = head; ListNode* slow = head; // 让快指针先走 k 步 for (int i = 0; i < k; ++i) { if (fast) fast = fast->next; } // 当快指针到达链表尾部时，慢指针就到了倒数第二位置 while (fast) { fast = fast->next; if (fast) slow = slow->next; } return slow; } int main() { // 创建示例链表 ListNode* head = new ListNode(1); head->next = new ListNode(2); head->next->next = new ListNode(3); head->next->next->next = new ListNode(4); head->next->next->next->next = new ListNode(5); int k = 2; // 要找倒数第二个元素 ListNode* result = findKthToTail(head, k); if (result) std::cout << "The " << k << "th to tail element is: " << result->val << std::endl; else std::cout << "Invalid k" << std::endl; delete head; return 0; } ```

阅读全文