LeetCode题解

题目：删除链表的倒数第N个节点

给定一个链表，删除链表的倒数第n个节点，并且返回链表的头结点。 示例:

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

解题思路：

解决这个问题焦点在于如何找到倒数的那个点，然后题目让我们尝试扫描一次去实现，那么应该如何去找到它呢，思路如下：

  • 定义两个指针p和q，q指向虚拟接点，p指向q后的第n个节点，如下图： 0019-01.png
  • 然后进行水平扫描，如果p的下一位不为空则p和q指向下一位 0019-02.png
    不断重复移动，当p的下一位指向null时，q下一位指向的点就是倒数第n点 0019-03.png
  • 然后缓存要删除的节点delnode，就是q的下一位，把q的下一位指向delnode的下一位，删除倒数第n个节点完成 0019-04.png

代码实现：

const removeNthFromEnd = function (head, n) {
    if (n <= 0 || !head) {
        return
    }
    let dummyHead = new ListNode(null);
    dummyHead.next = head;
    let p = dummyHead, q = dummyHead;
    while (n--) {
        p = p.next;
        if (!p) {
            return null
        }
    }
    while (p.next) {
        p = p.next;
        q = q.next
    }
    let delNode = q.next;
    q.next = delNode.next;
    delNode = null;
    let retNode = dummyHead.next;
    dummyHead = null;
    return retNode
};

← 20.有效的括号 →