问题描述：
输入一个单向链表，输出该链表中倒数第k个结点。链表倒数第0个节点为NULL。
struct list_node {
int data;
list_node* next;
};
分析：
方法1：
首先计算出链表中节点的个数n，然后倒数第k个节点，为正数n-k+1个节点。
需要遍历链表2次。
方法1代码实现：
// 13_1.cc
#include <iostream>
using namespace std; struct list_node {
int data;
list_node* next;
}; list_node* find_kth(list_node* head, size_t k) {
if (!head)
return NULL; // 统计链表中节点的个数
size_t count = ;
list_node* cur = head;
while(cur->next != NULL) {
cur = cur->next;
count++;
} if(count < k)
return NULL; cur = head;
for(size_t i = ; i <= count - k; i++)
cur = cur->next; return cur;
} // 插入元素
void insert_node(list_node*& head, int data) {
list_node* p = new list_node;
p->data = data;
p->next = head;
head = p;
} int main() {
// 创建链表
list_node* head = NULL;
for (int i = ; i > ; i--)
insert_node(head, i); // 查找倒数第k个
list_node* p = find_kth(head, );
cout << p->data << endl;
return ;
}
方法2：
使用双指针，第一个指针先走k步，然后两个指针一起走，直到第一个指针为NULL，则第一个指针便指向倒数第k个节点。
方法2实现代码：
// 13_2.cc
#include <iostream>
using namespace std; struct list_node {
int data;
list_node* next;
}; list_node* find_kth(list_node* head, size_t k) {
if (!head)
return NULL; list_node* p1 = head;
for (size_t i = ; i <= k; i++) {
if (!p1) // 链表长度不足k
return NULL;
else
p1 = p1->next;
} list_node* p2 = head;
while (p1) {
p1 = p1->next;
p2 = p2->next;
}
return p2;
} // 插入元素
void insert_node(list_node*& head, int data) {
list_node* p = new list_node;
p->data = data;
p->next = head;
head = p;
} int main() {
// 创建链表
list_node* head = NULL;
for (int i = ; i > ; i--)
insert_node(head, i); // 查找倒数第k个
list_node* p = find_kth(head, );
cout << p->data << endl;
return ;
}
转载自源代码