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

题目描述

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

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

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

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

解题思路

1. 栈

要找到倒数第n个数并删除，那么可以容易想到使用栈方法。思路比较简单

先把所有元素放入栈中，在从栈中取出第n个元素即可

ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        stack<ListNode*> stk;
        ListNode* cur = dummy;
        while (cur) {
            stk.push(cur);
            cur = cur->next;
        }
        for (int i = 0; i < n; ++i) {
            stk.pop();
        }
        ListNode* prev = stk.top();
        prev->next = prev->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }

2. 快慢指针

这个方法需要一些思路：可以设置两个指针，让它们两个之间相差n个位置，这样在后面指针到达链表末尾时，前面的指针刚好在倒数第n个位置。

ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* first = head;
        ListNode* second = dummy;
        for (int i = 0; i < n; ++i) {
            first = first->next;
        }
        while (first) {
            first = first->next;
            second = second->next;
        }
        second->next = second->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }