19-remove-nth-node-from-end-of-list.md

19. Remove Nth Node From End of List - 删除链表的倒数第N个节点

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

示例：

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

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

说明：

给定的 n 保证是有效的。

进阶：

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

---

题目标签：Linked List / Two Pointers

题目链接：LeetCode / LeetCode中国

题解

比较简单的单链表的题目。由于没有指向前驱的指针，为了定位倒数第n个节点，可以把节点存起来。删除节点时，注意判断待删节点是否是头结点，和待删节点不是头节点时的处理流程有所不同。

Language	Runtime	Memory
cpp	4 ms	N/A

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        vector<ListNode*> st;
        ListNode* hd = head;
        while(hd){
            st.push_back(hd);
            hd = hd->next;
        }
        ListNode* del = st.at(st.size() - n);
        if(del == head){
            ListNode* res = del->next;
            del->next = NULL;
            delete del;
            return res;
        }else{
            ListNode* pre = st.at(st.size() - n - 1);
            pre->next = del->next;
            del->next = NULL;
            delete del;
            return head;
        }
    }
};