19. Remove Nth Node From End of List

Leetcode link

题目简介

/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */

题目要求我们将链表 head 的后面第 n 项删除

解题思路

这种查找链表最后 n 项的题目，我们优先考虑双指针来解决

具体而言，如果题目要求我们删除最后第三项，我们用两个指针来模拟：

1 -> 2 -> 3 -> 4 -> 5
^              ^

left 指针指向当前链表头，right 指针指向链表头后 3 项的元素（也就是上面代码中的 4）

接下来，我们让两个指针同步往前进，直到 right 指针指向链表最后一个元素：

1 -> 2 -> 3 -> 4 -> 5
     ^              ^

此时指针 left 应该要指向要删除元素的前一个元素

此时我们只需要将 left.next = left.next.next 就可以完成元素删除了

当然我们还需要考虑一种边界情况，那就是要删除的是该链表的链表头

在这种情况下，n 等于链表的长度，此时当我们移动 right 指针的时候，会得到 right === null：

// 假设此时 n === 5
1 -> 2 -> 3 -> 4 -> 5 -> null
^                         ^

此时我们需要返回 head.next

Javascript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    let left = head
    let right = head
    let count = n

    while(count>0) {
        right = right.next
        count--
    }

    if(!right) {
        return head.next
    }

    while(right.next) {
        right = right.next
        left = left.next
    }
    left.next = left.next.next
    return head
};