结点(简单)"/>
JZ22 链表中倒数最后k个结点(简单)
描述
输入一个长度为 n 的链表,设链表中的元素的值为 ai ,返回该链表中倒数第k个节点。
如果该链表长度小于k,请返回一个长度为 0 的链表。
数据范围:0≤n≤10^5,0≤ai≤10^9,0≤k≤10^9
要求:空间复杂度 O(n),时间复杂度 O(n)
进阶:空间复杂度 O(1),时间复杂度 O(n)
例如输入{1,2,3,4,5},2时,对应的链表结构如下图所示:
其中蓝色部分为该链表的最后2个结点,所以返回倒数第2个结点(也即结点值为4的结点)即可,系统会打印后面所有的节点来比较。
示例1
输入:{1,2,3,4,5},2
返回值:{4,5}说明:返回倒数第2个节点4,系统会打印后面所有的节点来比较。
示例2
输入:{2},8
返回值:{}
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) {// write code hereListNode temp = pHead;int count = 0;
// 计算链表总长度while(pHead != null){count ++;pHead = pHead.next;}int sum = 0;sum = count - k;if(sum < 0){return null;}else{while(sum > 0){temp = temp.next;sum--;}}return temp;
}
}
更多推荐
JZ22 链表中倒数最后k个结点(简单)
发布评论