链表中倒数第k个结点
题目描述
输入一个链表，输出该链表中倒数第k个结点。
思路
- 两个指针，先让第一个指针和第二个指针都指向头结点，然后再让第一个指正走(k-1)步，到达第k个节点；
- 然后两个指针同时往后移动，当第一个结点到达末尾的时候，第二个结点所在位置就是倒数第k个节点了。
- 本题考察鲁棒性，因此要判断空值和负值以及k值不能超过链表的长度。
- 本题链表不含头结点。
实现代码
// Node用来标识结点，element用来保存节点上的数据，next用来保存指向下一个节点的链接
function Node(element) {
this.element = element;
this.next = null;
}
/* 在Node的原型链上添加insert方法，
判断链表是否为空，若为空，则在添加第一个结点，
若不为空，则在当前结点后面添加新的结点。*/
Node.prototype.insert = function(newElement) {
if (this.element === undefined) {
this.element = newElement;
} else {
var curNode = this;
while (curNode.next !== null) {
curNode = curNode.next;
}
var newNode = new Node(newElement);
curNode.next = newNode;
newNode.next = null;
}
};
// 查找链表中倒数第k个结点
function FindKthToTail(head, k) {
if (head.element === undefined) {
return new Error("head为空链表！");
}
if (k <= 0) {
return new Error("k小于等于0！");
}
var pre = head;
var last = head;
for (var i = 1; i < k; i++) {
if (pre.next !== null) {
pre = pre.next;
} else {
return new Error("k值过大！");
}
}
while (pre.next !== null) {
pre = pre.next;
last = last.next;
}
return last;
}
var node = new Node();
node.insert("Kobe");
node.insert("Curry");
node.insert("Russel");
node.insert("Klay");
node.insert("Tracy");
console.log(node);
var empty = {};
举例
FindKthToTail（node, -2）;
图片.png
FindKthToTail（empty , 2）;
图片.png
FindKthToTail（node, 100）;
图片.png
FindKthToTail（node, 2）;
图片.png
