数据结构 ——— 单链表oj题：链表中倒数第K个节点
目录
题目要求
输入一个链表，输出该链表中的倒数第K个节点（注意：k的值小于等于链表节点的总个数）
举例说明：
输入：k = 2 ; [1,2,3,4,5]
返回值：{4}
手搓简易链表
代码演示：
struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n1);
struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n2);
struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n3);
struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n4);
struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n5);
n1->val = 1;
n2->val = 3;
n3->val = 5;
n4->val = 7;
n5->val = 9;
n1->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = n5;
n5->next = NULL;代码实现
代码演示：
struct ListNode* FindkthToTail(struct ListNode* head, int k)
{
struct ListNode* slow = head;
struct ListNode* fast = head;
while (k--)
{
if (fast == NULL)
return NULL;
fast = fast->next;
}
while (fast != NULL)
{
slow = slow->next;
fast = fast->next;
}
slow->next = NULL;
return slow;
}代码解析：
代码思路：利用快慢节点指针，slow 和 fast ，fast 节点指针先走 k 步，然后 slow 和 fast 节点指针同时走，当 fast 节点指针走到了 NULL ，那么此时的 slow 节点指针所指向的节点就是倒数第 k 个节点
代码逻辑：fast 先走 k 步，并且要判断是否为空，防止 head 节点指针为空，再 slow 和fast 同时走，最后 slow 就是目标节点的指针，并且要将 sow 的 next 置空，否则就不是打印 倒数第 k 个节点了，就变成了打印从倒数第 k 个节点开始的链表
代码验证：
算法的时间复杂度和空间复杂度：
时间复杂度（大O渐进表示法）：O(N)
空间复杂度（大O渐进表示法）：O(1)
原文地址：https://blog.csdn.net/weixin_55341642/article/details/142691893
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！