题目
输入一个链表，输出该链表中倒数第K个节点。为了和服大多数人习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6.这个链表的倒数第3个节点是值为4的节点。链表节点定义如下：
分析
二次遍历
我们很容易就想到，可以先遍历一次得出链表的长度，然后再从头开始向后移动len-k个节点。
C++
#include <iostream> using namespace std; /*以下为链表的实现*/ typedef int TElemType;//链表节点值的数据类型 struct ListNode { TElemType Data; ListNode* next; }; void CreateList(ListNode** head) { ListNode* p = nullptr; ListNode* q = nullptr; int data = 1; (*head) = new ListNode(); if (nullptr == head) { cout << "申请空间失败！" << endl; return; } (*head)->next = nullptr; (*head)->Data = data++; q = *head; while (data < 7) { p = new ListNode(); p->Data = data++; p->next = nullptr; q->next = p; q = p; } } void PrintList(ListNode* head) { while (head != nullptr) { cout << head->Data; if (head->next == nullptr) { cout << " "; } else { cout << "->"; } head = head->next; } cout << endl; } /*查找目标节点*/ ListNode* FindKthToTail(ListNode* pListHead, int k) { if (pListHead == nullptr)//传入指针为空 { return nullptr; } int len = 0; ListNode* p = pListHead; while (p != nullptr)//遍历计算链表长度 { p = p->next; len++; } if (len < k)//判断查位置是否大于链表长度 { return nullptr; } int n = len - k; p = pListHead;//让p回到链表头部 while (n > 0 && p != nullptr)//第二次遍历，找目标节点 { p = p->next; n--; } return p; } int main() { ListNode* head = nullptr; CreateList(&head);//构造链表 PrintList(head);//输出 ListNode* ret = FindKthToTail(head, 3);//查找 if (ret != nullptr) { cout << "该节点为：" << ret->Data << endl; } else { cout << "传入指针为空或者查找位置大于链表长度" << endl; } return 0; }
双指针+一次遍历
假设我们链表长度为6，找倒数第4个节点
我们可以设定快指针fast和慢指针slow让快指针先走k-1步，到节点4位置。然后快慢指针一起走，快指针走完时，慢指针刚好在节点3的位置上。实现也是比较简单的，但是不容易想到。
C++
#include <iostream> using namespace std; /*以下为链表的实现*/ typedef int TElemType;//链表节点值的数据类型 struct ListNode { TElemType Data; struct ListNode* next; }; void CreateList(ListNode** head) { ListNode* p = nullptr; ListNode* q = nullptr; int data = 1; (*head) = new ListNode(); if (nullptr == head) { cout << "申请空间失败！" << endl; return; } (*head)->next = nullptr; (*head)->Data = data++; q = *head; while (data < 7) { p = new ListNode(); p->Data = data++; p->next = nullptr; q->next = p; q = p; } } void PrintList(ListNode* head) { while (head != nullptr) { cout << head->Data; if (head->next == nullptr) { cout << " "; } else { cout << "->"; } head = head->next; } cout << endl; } /*查找目标节点*/ ListNode* FindKthToTail(ListNode* pListHead, int k) { if (pListHead == nullptr)//传入指针为空 { return nullptr; } int i = 1; ListNode* fast = pListHead; ListNode* slow = pListHead; //走k-1步或者链表长度小于k提前终止， 下面需要判断因为什么退出的循环 while (i < k && fast != nullptr) { fast = fast->next; i++; } if (nullptr == fast)//结束循环是因为遍历到空了 { return nullptr; } while (fast->next != nullptr)//快指针到头了 { fast = fast->next; slow = slow->next; } return slow; } int main() { ListNode* head = nullptr; CreateList(&head);//构造链表 PrintList(head);//输出 ListNode* ret = FindKthToTail(head, 3);//查找 if (ret != nullptr) { cout << "该节点为：" << ret->Data << endl; } else { cout << "传入指针为空或者查找位置大于链表长度" << endl; } return 0; }
本章完！
