目录

题目要求

手搓简易链表

代码实现 


题目要求

输入一个链表,输出该链表中的倒数第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)

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部