链表中倒数第k个节点1

在计算机科学中，链表是一种常见的数据结构，用于存储一系列有序的数据元素。链表与数组不同，不连续存储数据，而是通过每个节点的指针连接。在这个问题中，我们需要找到链表中倒数第 k 个节点。这个问题是LeetCode上的一个经典题目，涉及到链表操作和算法设计。 让我们定义链表节点的结构体： ```cpp struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; ``` 题目要求我们实现一个名为 `getKthFromEnd` 的函数，该函数接受两个参数：一个链表的头节点 `head` 和一个整数 `k`，返回链表中的倒数第 k 个节点。题目规定链表的倒数第 1 个节点是尾节点。 一种解决方法是遍历整个链表，计算链表的长度，然后从头节点开始移动 k 个节点。但是这种方法效率较低，因为它需要两次遍历链表。以下是使用这种方法的示例代码： ```cpp class Solution { public: ListNode* getKthFromEnd(ListNode* head, int k) { ListNode* p = head; int count = 0; while (p != nullptr) { p = p->next; count++; } ListNode* res = head; for (int i = 0; i < count - k; i++) { res = res->next; } return res; } }; ``` 然而，我们可以使用更高效的方法来解决此问题，即**快慢指针法**。这种方法只需要遍历链表一次。我们设置两个指针，一个快指针（fast）和一个慢指针（slow），初始时都指向链表的头节点。快指针每次向前移动 k 步，而慢指针每次只移动一步。当快指针到达链表末尾时，慢指针将正好位于倒数第 k 个节点。 下面是使用快慢指针法的解决方案： ```cpp class Solution { public: ListNode* getKthFromEnd(ListNode* head, int k) { if (head == nullptr || k <= 0) return nullptr; ListNode* fast = head; ListNode* slow = head; // 移动快指针到倒数第 k 个位置 while (k--) { if (fast != nullptr) { fast = fast->next; } else { return nullptr; } } // 让快指针继续前进，直到它到达链表末尾，此时慢指针会停在倒数第 k 个节点 while (fast != nullptr) { slow = slow->next; fast = fast->next; } return slow; } }; ``` 这个方法的时间复杂度为 O(n)，空间复杂度为 O(1)，因为我们只需要常数级别的额外空间来存储指针。这个算法充分利用了指针的移动来避免重复计算链表长度，提高了效率。