链表 开发语言 C语言/数据结构——（返回到数第K个节点）

一.前言

嗨嗨嗨，大家我们又见面了。今天我们来分享一道链表题——返回到数第K个节点。

题目链接https://leetcode.cn/problems/kth-node-from-end-of-list-lcci废话不多说，让我们直接开始吧。

二.正文

1.1题目描述

这是在力扣上的一道题。

1.2题目分析

对于这道题，我的想法是可以通过将链表先进行反转，然后直接通过找到目标数据。就比如，文中所给示例：

1->2->3->4->5和K=2

先反转：5->4->3->2->1，此时K=2，就是第二个数据为4的节点。

既然理论成立我们就可以着手写代码了。首先我们面临着第一个问题，如何将链表反转呢？

（i）不建立哨兵位

这个是我之前写的一个对于反转链表的博客链接https://blog.csdn.net/yiqingaa/article/details/138376042?有兴趣的小伙伴可以看一下。

（ii）建立哨兵位求解

我们可以创建一个哨兵位，即一个真实存在，但并没有初始化的节点（这个节点是通过malloc函数申请的，后面我们需要手动删除）

上面两种方式都可行，这里我采用的是第二种方式。

1.3代码实现

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* struct ListNode *next;

* };

*/

typedef struct ListNode ListNode;

int kthToLast(struct ListNode* head, int k)

{

// if(head==NULL)

// return NULL;

ListNode*pcur,*prev,*pnext;

ListNode* phead=(ListNode*)malloc(sizeof(ListNode));

phead->next=head;

pcur=head;prev=phead;pnext=pcur->next;

while(pcur!=NULL)

{

pcur->next=prev;

prev=pcur;

pcur=pnext;

if(pnext!=NULL)

pnext=pnext->next;

}

head->next=NULL;

free(phead);

phead=NULL;

while(--k)

{

prev=prev->next;

}

return prev->val;

}

值得注意的是，以上代码是在力扣环境条件下运行的代码。

三.结言

今天的题目分享就到此结束了，拜拜。

文章来源