当前位置：网站首页>＃yyds干货盘点＃面试必刷TOP101：链表中倒数最后k个结点

＃yyds干货盘点＃面试必刷TOP101：链表中倒数最后k个结点

2022-08-01 18:43:00 【51CTO】

1.简述：

描述

输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。

如果该链表长度小于k，请返回一个长度为 0 的链表。

数据范围：，，

要求：空间复杂度，时间复杂度

进阶：空间复杂度，时间复杂度

例如输入{1,2,3,4,5},2时，对应的链表结构如下图所示：

#yyds干货盘点# 面试必刷TOP101：链表中倒数最后k个结点_链表_08

其中蓝色部分为该链表的最后2个结点，所以返回倒数第2个结点（也即结点值为4的结点）即可，系统会打印后面所有的节点来比较。

示例1

输入：

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

返回值：

说明：

       
       返回倒数第2个节点4，系统会打印后面所有的节点来比较。
      
1.

示例2

输入：

返回值：

2.代码实现：

       
       import java.util.*;
       
/*
       
 * public class ListNode {
       
 *   int val;
       
 *   ListNode next = null;
       
 *   public ListNode(int val) {
       
 *     this.val = val;
       
 *   }
       
 * }
       
 */
       
public class Solution {
       
    /**
       
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
       
     *
       
     * 
       
     * @param pHead ListNode类 
       
     * @param k int整型 
       
     * @return ListNode类
       
     */
       
    public ListNode FindKthToTail (ListNode pHead, int k) {
       
        int n = 0;
       
        ListNode cur = pHead;
       
        while(cur != null){
       
            n++;
       
            cur = cur.next;
       
        }
       
        if(n < k){
       
            return null;
       
        }
       
        cur = pHead;
       
        for(int i = 0; i < n - k; i++){
       
            cur = cur.next;
       
        }
       
        return cur;
       
    }
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.