Java题目详解——牛客网.链表中倒数第k个结点一.题目要求二.解题思路三.具体代码

110 阅读 0 评论 73 点赞

我是靠谱客的博主细心手套，这篇文章主要介绍Java题目详解——牛客网.链表中倒数第k个结点一.题目要求二.解题思路三.具体代码，现在分享给大家，希望可以做个参考。

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

一.题目要求

二.解题思路

1.常规求长度

2.设置前后指针

三.具体代码

1.常规求长度

2.设置前后指针

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

一.题目要求

描述：

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

示例1：

输入：

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

返回值：

{5}

二.解题思路

1.常规求长度

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

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

复制代码

1
2
3
4
5
6
int x=size-k;
ListNode ans=head;
for(int i=0;i<x;i++){
ans=ans.next;
}
return ans;

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

复制代码

1
2
3
4
5
6
7
8
9
private int sizeOf(ListNode head){
ListNode cur=head;
int size=0;
while(cur!=null){
size++;
cur=cur.next;
}
return size;
}

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

复制代码

1
2
3
if(size<k){
return null;
}

2.设置前后指针

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

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

复制代码

1
2
3
if(forward==null){
return null;
}

下面画图举例理解一下：

三.具体代码

1.常规求长度

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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.设置前后指针

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
}
}