您现在的位置是：首页 >其他 >【数据结构】--单链表力扣面试题④找链表中倒数第k个结点网站首页其他

目录

法一、遍历链表法

法二、快慢指针法

题述：输入一个链表，输出该链表中倒数第k个结点

示例：

输入:1,[1,2,3,4,5]

返回值:[5]

已知链表的定义和函数头FindKthToTail，让你完善FindKthToTail函数

struct ListNode
{
    int val;
    struct ListNode* next;
};
struct ListNode* FindKthToTail(struct ListNode* pListhead,int k)

法一、遍历链表法

思路：我们只要遍历链表求出链表的长度n，倒数第k个 ，即从第一个节点往后走n-k步即可找到这个节点。

#include<stdio.h>
#include<stdlib.h>

struct ListNode
{
	int val;
	struct ListNode* next;
};
struct ListNode* FindKthToTail(struct ListNode* pListhead,int k)
{	
	//1、遍历链表
	struct ListNode* temp = pListhead;
	struct ListNode* cur = pListhead;
	int len = 0;
	for (temp; temp != NULL; temp = temp->next)
	{
		len++;
	}
	for (int i = 0; i < len - k; i++)
		cur = cur->next;//往后走len-k步

	return cur;
}
int main()
{
	struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
	int k = 2;
	n1->val = 1;
	n2->val = 2;
	n3->val = 3;
	n4->val = 4;
	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = NULL;

	struct ListNode* obj = FindKthToTail(n1,k);
	if (obj)//一定要考虑链表为空的情况是不能打印的，会非法访问内存
		printf("%d
", obj->val);
	else
		printf("链表为空，无法寻找！
");

	return 0;
}

法二、快慢指针法

这种方法只循环遍历了一次链表，效率更高点
 

思路：定义两个快慢指针:fast(快指针)，slow(慢指针)。求倒数第k个结点，初始条件使fast和slow均指向第一个节点。因为单链表是无法倒着走的，所以对于slow，只需要正走n-k步(n为总长度)就是倒数第k个结点（这一点可以画图悉知），而这种方法就是不知道总长度n(因为这种方法要求了只能遍历链表一次)，所以我们才定义了一个快指针fast,让其先走k步，那么走完之后，此时fast走到NULL时，正好为n-k步。

故总体思路：slow和fast初始均指向第一个节点，再让fast先走k步，然后slow和fast再同时走，直到fast为NULL，此时slow所指向的节点就是倒数第k个结点。（因为此时正好满足slow正走n-k步）

还要考虑临界问题：如果k>链表长度怎么办?如果为空链表怎么办?

#include<stdio.h>
#include<stdlib.h>

struct ListNode
{
	int val;
	struct ListNode* next;
};
struct ListNode* FindKthToTail(struct ListNode* pListhead, int k)
{
	struct ListNode* fast = pListhead, * slow = pListhead;//初始条件
	while (k--)
	{//这个循环会执行k次
	//当k=1时，k--会再循环最后一次，然后k变为0，此时fast!=NULL,如果链表长度n=k的话，
	// 那么fast=fast->next后，fast变为NULL。
		if (fast == NULL)
		{
			return NULL;
	//如果k>链表长度，会提前变为NULL，那么直接返回NULL
	//k=链表长度时是合法的，会返回slow，即第一个节点
	//而不是返回NULL，因为是先判断fast是否为NULL，然后才fast=fast->next的
	//当然，这种情况对空链表照常适用
		}
		fast = fast->next;//fast先走k步
	}
	while (fast)
	{
		slow = slow->next;
		fast = fast->next;
	}
	return slow;
}
int main()
{
	struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
	int k = 2;
	n1->val = 1;
	n2->val = 2;
	n3->val = 3;
	n4->val = 4;
	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = NULL;

	struct ListNode* obj = FindKthToTail(n1, k);
	if (obj)//一定要考虑链表为空的情况是不能打印的，会非法访问内存
		printf("%d
", obj->val);
	else
		printf("链表为空，无法寻找！
");

	return 0;
}