ARTS打卡：第二十二周

每周完成一个ARTS：

Algorithm：每周至少做一个 leetcode 的算法题

Review：阅读并点评至少一篇英文技术文章

Tip：学习至少一个技术技巧

Share：分享一篇有观点和思考的技术文章

Algorithm

19. Remove Nth Node From End of List（Medium）

问题描述

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

示例：

1
2
3

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

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

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

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

解题思路

普通思路：

先遍历计算出这个链表的节点数 count
因为 n 是指链表的倒数第 n 个节点，所以链表的第（count - n + 1）个节点就是我们要删除的节点

进阶思路：

采用快慢指针的思想，只需使用一趟扫描实现：

为了方便理解以及写代码，我们先虚设一个节点，作为起始节点，它的后继节点指向头结点。
使用两个指针，一个是慢指针 slow，指向起始节点，一个是快指针，指向慢指针 slow 前 n + 1 个节点
同时移动两个指针，在移动过程中，保持两指针之间间隔 n 个节点，直至快指针 fast 移至尾部节点的后继节点处。
这时慢指针 slow 指向的是目标节点的前驱节点，紧接着只需将慢指针指向的节点的后继节点指向目前节点的后继节点即可。

代码实现

普通版实现：

class ListNode {
    int val;
    ListNode node;
    public ListNode(int val) {
        this.val = val;
    }
}

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 限制条件
        if (head == null || n <=0) {
            return head;
        }
        int count = 1;
        ListNode tmpNode = head;
        // 遍历链表
        while (tmpNode.next != null) {
            // 计算节点个数
			++count;
            tmpNode = tmpNode.next;
        }
        tmpNode = head;
        int preTargetIndex = count - n;
        // 当 preTargetIndex == 0 时，即要删除头结点
        if (preTargetIndex == 0) {
            return tmpNode.next;
        }
        // 找到要删除的目标节点的上一个节点
        while (preTargetIndex > 1) {
			--preTargetIndex;
            tmpNode = tmpNode.next;
        }
        // 移除目标节点
        tmpNode.next = tmpNode.next.next;
        return head;
    }
}

结果：

Runtime: 0 ms, faster than 100.00% of Java online submissions for Remove Nth Node From End of List.

Memory Usage: 34.8 MB, less than 100.00% of Java online submissions for Remove Nth Node From End of List.

复杂度：

时间复杂度：O(n)

空间复杂度：O(1)

进阶版：

class ListNode {
    int val;
    ListNode node;
    public ListNode(int val) {
        this.val = val;
    }
}

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 边界条件
        if (head == null || n <= 0) {
            return head;
        }
        // 虚设一个起始节点（哨兵节点），为了方便删除头结点的情况
        ListNode start = new ListNode(0);
        start.next = head;
        // 慢指针指向起始节点
        ListNode slow = start;
        ListNode fast = start;
        // 快指针指向慢指针的前 n 个节点
        for (int i = 0; i < n + 1; i++) {
            fast = fast.next;
        }
        // 遍历链表直至快指针 fast 移至尾部节点的后继节点处
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        // 删除节点
        slow.next = slow.next.next;
        return start.next;
    }
}