C语言实现获取链表中倒数第k个节点

Mia

发布时间：2026-10-14| 2人浏览过

原创

本文介绍使用C语言查找单链表中倒数第k个节点的算法。通过双指针技巧，一个指针先走k步，另一个指针随后同步移动，当第一个指针到达末尾时，第二个指针即指向目标节点。文章包含完整的代码实现及边界条件处理，如链表为空或k值超出链表长度等异常情况。

问题分析与思路

在单向链表中寻找倒数第 k 个节点，最直接的方法是遍历两次：第一次计算链表总长度 n，第二次从头节点出发找到第 n-k+1 个节点。这种方法虽然直观，但需要遍历两次链表。

更优化的方法是使用双指针法（也称快慢指针法），只需一次遍历即可：

定义两个指针 pFast 和 pSlow，初始均指向头节点。
pFast 先向前移动 k 步。
若此时 pFast 为空，说明链表长度小于 k，返回异常。
随后 pFast 和 pSlow 同时向后移动，直到 pFast 指向 NULL。
此时 pSlow 所指的节点即为倒数第 k 个节点。

代码实现

以下代码基于 C++ 编写（兼容 C 语言逻辑），演示了链表的构建、打印以及查找倒数第 k 个节点的具体实现。注意原稿中代码使用了 C++ 特性（如引用、namespace），在实际纯 C 项目中需相应调整。

/* 
* Copyright (c) 2011 alexingcool. All Rights Reserved. 
*/ 
#include <iostream>

using namespace std;

int array[] = {5, 7, 6, 9, 11, 10, 8};
const int size = sizeof array / sizeof *array;

struct Node
{
 Node(int i = 0, Node *n = NULL) : item(i), next(n) {}

 int item;
 Node *next;
};

Node* construct(int (&array)[size])
{
 Node dummy;
 Node *head = &dummy;

 for(int i = 0; i < size; i++) {
 Node *temp = new Node(array[i]);
 head->next = temp;
 head = temp;
 }

 return dummy.next;
}

void print(Node *head)
{
 while(head) {
 cout << head->item << " ";
 head = head->next;
 }
}

Node* findKnode(Node *head, int k)
{
 Node *pKnode = head;

 if(head == NULL) {
 cout << "link is null" << endl;
 return NULL;
 }

 // 快指针先走 k 步
 while(k--) {
 if(head == NULL) {
  cout << "k is bigger than the length of the link" << endl;
  return NULL;
 }
  head = head->next;
 }

 // 双指针同步移动
 while(head) {
 head = head->next;
 pKnode = pKnode->next;
 }

 return pKnode;
}

void main()
{
 Node *head = construct(array);
 cout << "source link: ";
 print(head);
 cout << endl;
 Node *kNode = findKnode(head, 5);
 if(kNode != NULL)
 cout << "the knode is: " << kNode->item << endl;
}

测试用例说明

为了确保算法的健壮性，建议覆盖以下三种典型场景：

空链表处理：
输入 head = NULL，程序应识别并提示链接为空，避免空指针解引用。
正常情况：
链表不为空，且 k 值小于等于链表长度（k <= len(head)）。此时应正确返回倒数第 k 个节点的值。
异常 K 值：
链表不为空，但 k 值大于链表长度（k > len(head)）。此时应在快指针走完 k 步前检测到 head == NULL，并输出错误提示返回 NULL。