目录

题目链接：链表中倒数第k个结点

一.题目要求

二.解题思路

1.常规求长度

2.设置前后指针

三.具体代码

1.常规求长度

2.设置前后指针

题目链接：链表中倒数第k个结点

一.题目要求

描述：

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

示例1：

输入：

1,{1,2,3,4,5}

返回值：

{5}

二.解题思路

1.常规求长度

        该方法主要是将倒数第k个结点转换为正数第x个结点，这样我们就能从前往后找到想要的结点。

        首先，求出链表的总长度（size），再减去k，就是我们想要从前往后走的步数（x=size-k）。其次，通过控制循环遍历中走的步数，从而得到我们想要的结点。

int x=size-k;
ListNode ans=head;
for(int i=0;i<x;i++){
ans=ans.next;
}
return ans;

        求总长度（size）是通过循环遍历整条链表得到的，函数如下：

private int sizeOf(ListNode head){
ListNode cur=head;
int size=0;
while(cur!=null){
size++;
cur=cur.next;
}
return size;
}

注意：所有情况都要考虑到，当size<k时，直接返回null。 

if(size<k){
return null;
}

2.设置前后指针

        我们先设置一个前指针（forward），让前指针先走k步，然后此时再设置一个后指针（barkward），然后让他们同时走，直到前指针（forward）走到链表末尾，这时后指针（barkward）正好走到倒数第k个结点。

注意：当链表为空链表或给的k比链表总长度大时，应该在前指针向前走时判断出来。

if(forward==null){
return null;
}

        下面画图举例理解一下：

三.具体代码

1.常规求长度

public class Solution {
private int sizeOf(ListNode head){
ListNode cur=head;
int size=0;
while(cur!=null){
size++;
cur=cur.next;
}
return size;
}
public ListNode FindKthToTail(ListNode head,int k) {
int size=sizeOf(head);
if(size<k){
return null;
}
int x=size-k;
ListNode ans=head;
for(int i=0;i<x;i++){
ans=ans.next;
}
return ans;
}
}

2.设置前后指针

public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
ListNode forward=head;
for(int i=0;i<k;i++){
if(forward==null){
return null;
}
forward=forward.next;
}
ListNode backward=head;
while(forward!=null){
forward=forward.next;
backward=backward.next;
}
return backward;
}
}

如想了解链表（LinkedList）相关知识，请查阅：

LinkedList（链表）的介绍及自我实现

如有建议或想法，欢迎一起讨论学习~

最后

以上就是细心手套为你收集整理的Java题目详解——牛客网.链表中倒数第k个结点一.题目要求二.解题思路三.具体代码的全部内容，希望文章能够帮你解决Java题目详解——牛客网.链表中倒数第k个结点一.题目要求二.解题思路三.具体代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。