当前位置：网站首页>#yyds dry goods inventory# Interview must brush TOP101: the last k nodes in the linked list

#yyds dry goods inventory# Interview must brush TOP101: the last k nodes in the linked list

2022-08-01 18:52: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.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/213/202208011836542441.html

当前位置：网站首页>#yyds dry goods inventory# Interview must brush TOP101: the last k nodes in the linked list

#yyds dry goods inventory# Interview must brush TOP101: the last k nodes in the linked list

边栏推荐

猜你喜欢

随机推荐