力扣HOT100 - 19. 删除链表的倒数第N个节点

解题思路：

链表题目：哑节点、栈、快慢指针（双指针）

方法一：计算链表长度

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dum = new ListNode(0, head);
        int len = getLen(head);
        ListNode cur = dum;
        for (int i = 0; i < len - n; i++) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        return dum.next;
    }

    public int getLen(ListNode head) {
        int len = 0;
        while (head != null) {
            head = head.next;
            len++;
        }
        return len;
    }
}

方法二：栈

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dum = new ListNode(0, head);
        Deque<ListNode> stack = new LinkedList<>();
        ListNode cur=dum;
        while(cur!=null){
            stack.push(cur);
            cur=cur.next;
        }
        for(int i=0;i<n;i++){
            stack.pop();
        }
        ListNode pre=stack.peek();
        pre.next=pre.next.next;
        return dum.next;
    }
}

方法三：快慢指针（双指针）

注意fast从head开始，而不是dum

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dum = new ListNode(0, head);
        ListNode fast=head;
        ListNode slow=dum;
        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 dum.next;
    }
}