19. 删除链表的倒数第 N 个结点

19. 删除链表的倒数第 N 个结点

快慢指针

为了避免删除头节点时多写判断，新建 temp 临时节点，temp 的 next 指向 head，最后返回 temp 的 next

执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户 内存消耗：36 MB, 在所有 Java 提交中击败了98.72% 的用户

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode temp = new ListNode(0, head);
        ListNode fast = head;
        ListNode slow = temp;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return temp.next;
    }
}

计算链表长度

执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户 内存消耗：36.3 MB, 在所有 Java 提交中击败了75.82% 的用户

    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 计算长度
        int length = 0;
        ListNode temp = head;
        while (temp != null) {
            temp = temp.next;
            length ++;
        }
        // temp作为临时节点，next指向head
        temp = new ListNode(0);
        temp.next = head;
        ListNode cur = temp;
        for (int i = 0; i < length - n; i++) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        return temp.next;
    }

使用辅助栈

先把所有节点加入栈，使用栈先进后出的特性，出栈时第 n 个节点就是要删除的节点

执行用时：1 ms, 在所有 Java 提交中击败了20.25% 的用户 内存消耗：37.8 MB, 在所有 Java 提交中击败了5.00% 的用户

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode temp = new ListNode(0, head);
        Stack<ListNode> stack = new Stack<>();
        ListNode cur = temp;

        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }

        for (int i = 0; i <= n; i++) {
            cur = stack.pop();
        }
        cur.next = cur.next.next;
        return temp.next;
    }
}