12.算法学习之删除链表的倒数第N个节点

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

示例：

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

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

说明：给定的 n 保证是有效的。

我的思路： 首先看到这类型的题，首先肯定想到的是快慢指针， 而不是用一个额外的集合去存储链表节点，然后删除倒数第N个节点。 利用快慢指针，我们同时还得新增一个 哨兵节点，指向头结点，目的是有利于头结点的删除。我的代码如下：

public static ListNode removeNthFromEnd(ListNode head, int n) {
        //哨兵节点
        ListNode sb = new ListNode();
        sb.next = head;
        //k快指针，m慢指针
        ListNode k = sb, m = sb;
        int count = 0;
        while (k.next != null) {
            k = k.next;
            //快指针先走N步
            if (++count > n) {
                m = m.next;
            }
        }
        m.next = m.next.next;
        return sb.next;
    }

以上就是我的代码了。这类题型应该选用这类双指针的技巧。

还有的思路是利用栈Stack来做，也是可以的，不过比双指针要劣势一点。

public static ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        Stack<ListNode> stack = new Stack<>();
        ListNode cur = dummy;
        //先入栈
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        //出栈后N个节点
        for (int i = 0; i < n; i++) {
            stack.pop();
        }
        //获取到倒数第N+1个node
        ListNode node = stack.peek();
        node.next = node.next.next;
        return dummy.next;
    }

如有错误，请各位大佬指出！ 谢谢。