链表中倒数第k个结点
题目描述
输入一个链表，输出该链表中倒数第k个结点。
时间限制：3秒 空间限制：32768K
思路
先遍历得到链表的长度，然后取得倒数第k项的位置。
代码
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function FindKthToTail(head, k)
{
// write code here
var node = head;
var i = 0;
while(node != null) {
i++;
node = node.next;
}
if(k <= 0 || k > i) return false;
for(var j = 0; j < i - k; j++) {
head = head.next;
}
return head;
}
优化代码
以上代码的缺点在于需要遍历两遍链表，优化方法为在第一次遍历时，设置一个变量暂存当前节点的前k-1个节点，避免第二次遍历
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function FindKthToTail(head, k)
{
// write code here
var node = head;
var preNode = head;
var i = 1;
while(node != null) {
if(i > k) {
preNode = preNode.next;
}
i++;
node = node.next;
}
if(k <= 0 || k > i - 1) return false;
return preNode;
}
