原题地址：删除链表的倒数第N个节点
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
准备工作
定义链表结点：
function ListNode(val) {
this.val = val;
this.next = null;
}
数组转链表，方便测试数据的输入：
function arrayToList(array) {
let node = null;
for (let i = array.length - 1; i >= 0; i --) {
let newNode = new ListNode(array[i]);
newNode.next = node;
node = newNode;
}
return node;
}
链表转字符串，方便测试结果的显示：
function listToString(node) {
return node ? `${node.val}${node.next ? ` -> ${listToString(node.next)}` : '' }` : null;
}
两轮遍历
不考虑题目要求的一轮遍历，本题还是比较简单的。只需要通过一次遍历找到倒数第 n 个结点，再通过一轮遍历删除它就可以了：
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/
const removeNthFromEnd1 = function(head, n) {
// 统计链表结点数量
let count = 0;
let node = head;
while (node) {
count ++;
node = node.next;
}
// 要删除的是头结点
if (count === n) {
return head && head.next;
}
// 删除倒数第n个结点
node = head;
for (let i = 0; i < count - n - 1; i ++) {
node = node.next;
}
node.next = node.next.next;
return head;
};
测试：
let start = new Date();
const test = removeNthFromEnd1;
console.log(listToString(test(arrayToList([1, 2, 3, 4, 5]), 2))); // 1 -> 2 -> 3 -> 5
console.log(listToString(test(arrayToList([1]), 1))); // null
console.log(listToString(test(arrayToList([1, 2]), 2))); // 2
console.log(new Date().getTime() - start.getTime()); // 4
时间复杂度： 遍历两次，时间复杂度为O(2n) = O(n)
空间复杂度： 只需要固定大小的额外空间，空间复杂度为O(1)
双指针法
两次遍历比较简单，但是不符合题目一次遍历的要求。题目要求的是删除倒数第 n 个结点，我们可以通过双指针来优化。设置快慢两个指针，快指针先走 n 步，然后快慢指针同步走，这样两指针之间的距离就保持在了 n。只要快指针到了链表终点，通过慢指针就可以删除倒数第 n 个结点：
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/
const removeNthFromEnd2 = function(head, n) {
let [slow, fast] = [head, head];
// 快指针先走n步
for (let i = 0; i < n; i ++) {
fast = fast.next;
}
// 快指针已经走完了链表，证明要删除的是头结点
if (!fast) {
return head && head.next;
}
// 快慢指针同步移动
while (fast.next) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return head;
};
测试：
let start = new Date();
const test = removeNthFromEnd2;
console.log(listToString(test(arrayToList([1, 2, 3, 4, 5]), 2))); // 1 -> 2 -> 3 -> 5
console.log(listToString(test(arrayToList([1]), 1))); // null
console.log(listToString(test(arrayToList([1, 2]), 2))); // 2
console.log(new Date().getTime() - start.getTime()); // 3
时间复杂度： 一次遍历，时间复杂度为O(n)
空间复杂度： 空间复杂度为O(1)
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Jul 28,2019