山凉田带你玩转OJ--返回链表倒数第K个结点

题目解读

给定一个单链表和一个整数 k，要求返回链表的倒数第 k 个节点。

示例

输入：1 -> 2 -> 3 -> 4 -> 5，k = 2

输出：4

解题思路

采用快慢指针法，具体步骤如下：

1. 初始化指针：

   • 快指针 fast 和慢指针 slow 都初始化为链表的头节点 head。

2. 快指针提前走 k 步：

   • 让快指针 fast 先向前移动 k 步，这样快指针和慢指针之间就相差 k 个节点。

3. 同时移动快慢指针：

   • 当快指针 fast 不为 NULL 时，同时移动快指针和慢指针，直到快指针到达链表的末尾（即 fast == NULL）。

4. 返回慢指针：

   • 当快指针到达链表末尾时，慢指针正好位于倒数第 k 个节点的位置，返回慢指针。

代码实现

		if(head==NULL)
		{
			return NULL;
		}
        // 快指针提前走 k 步
        for (int i = 0; i < k; i++) {
            if (fast == NULL) {
                return NULL;  // 链表长度小于 k
            }
            fast = fast->next;
        }

        // 同时移动快慢指针
        while (fast != NULL) {
            fast = fast->next;
            slow = slow->next;
        }

        return slow;  // 返回慢指针指向的节点
    }

代码解释

1. 空链表处理：

   • 如果 head 为 NULL 或 k <= 0，直接返回 NULL，因为这样的输入是无效的。

2. 初始化指针：

   • 快指针 fast 和慢指针 slow 都初始化为 head。

3. 快指针提前走 k 步：

   • 使用 for 循环让快指针 fast 先向前移动 k 步。
   • 如果在移动过程中 fast 变为 NULL，说明链表长度小于 k，返回 NULL。

4. 同时移动快慢指针：

   • 使用 while 循环，当快指针 fast 不为 NULL 时，同时移动快指针和慢指针。

5. 返回慢指针：

   • 当快指针到达链表末尾时，慢指针正好位于倒数第 k 个节点的位置，返回慢指针。

总结

通过使用快慢指针法，我们可以高效地找到链表的倒数第 k 个节点。这种方法不仅简单易懂，而且时间复杂度为 O(n)，空间复杂度为 O(1)。希望这篇博客对你有所帮助！如果有任何问题或需要进一步的解释，请随时提问。