刷题之 删除链表的倒数第 N 个结点

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

示例 1：

输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]

受到上个题的启发，这个题依然用快慢指针。删除结点要找到要删除结点的上一个节点，也就是哑结点，快指针 先行，慢指针后行，快慢指针之间相差题目所给的倒数几个，倒数第二个，快指针到达末尾，慢指针到达倒数第三个，也就是快慢指针相差n个。所以就是快指针先走到末尾，慢指针到达哑结点。代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode d=new ListNode(0,head);
        ListNode slow=d,fast=head;
        int count=0;
        while(fast!=null&&fast.next!=null){
            fast=fast.next;
            if(count!=n){
                count++;
            }           
            if(count==n){
                slow=slow.next;
            }
        }
            slow.next=slow.next.next;
        return d.next;
    }
}

这里有个细节需要在原链表头前插入一个结点。如果slow和fast同时从head出发，会出现空指针问题.因为当count等于n的时候，slow已经往下走了。所以要想达到slow从首结点出发的目的，需要在原链表头前插入一个结点.

还有另外一个原因是如果只有一个结点，删除之后应该原链表没有了，需要返回原链表头，所以需要一个指向原链表的结点。最后return d.next 就是这个原因。

老规矩 看题解学习其他思路。

看到从后往前，便可以想到栈（我居然把这个忘干净了！！！）先进后出，那么将这个链表压入栈中，倒数第n个，便是出栈第n-1个，直接将这个结点删除，即可达成目的。

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

值得一提的是，

Stack.peek() peek()函数返回栈顶的元素，但不弹出该栈顶元素。

Stack.pop() pop()函数返回栈顶的元素，并且将该栈顶元素出栈。

开拓思路！任重道远！！！