经典OJ题：链表中的倒数第K个节点

 

题目：

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

题源：链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com) 

 

方法一：暴力求解法

• 可以线统计链表的节点个数，然后用链表节点的个数减去K，得出倒数第K个节点的前一个节点到头节点的节点个数。
• 之后使用循环遍历，遍历到倒数第K个节点的前一个节点，随后输出下一个节点。
• 而输出的下一个节点便是倒数第K个节点。

方法二：快慢指针的长度差

• 设立两个指针，fast、slow
• 因为所求的是倒数第K个节点，所以这个节点到尾节点的距离是K
• 所以利用这个K，进行一个距离差，也就是将fast和slow之间的距离变成K并且按照同样的速度向前运动，直到fast走到NULL
• 当fast走到NULL的时候，也就表明了slow指向的节点就是倒数第K个节点。

 

 转化为代码，就是先让fast走到和头节点相差距离为K的节点位置，然后fast和slow同时向前移动一个节点的距离位置，直到fast==NULL

注意还是需要进行K的判断！

如果K大于链表长度，则再进行移动fast的距离时，fast就会被移动到NULL上