题解 | # 删除链表的倒数第n个节点 #

class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { // write code here stack<ListNode*> s; ListNode* p = head; ListNode* cur, pre; while (p) { s.push(p); p = p->next; } for(int i=0;i<n;++i){ s.pop(); if(s.empty()) return head->next; pre=s.top(); } for (ListNode q = head; q; q = q->next) { if (q == pre) { cur = q->next; q->next = cur->next; } } return head; } };

利用栈来存放链表，利用栈的先进后出的特性找到待删除节点的前一个结点，在根据这个节点找到待删除结点，利用链表删除的性质从而完成题目要求。有一种特殊情况就是待删除结点位置等于链表的长度，这种情况就下直接让head=head->next。 (如果想一步到位的话，可以设置一个空哨头节点，由于时间原因我这里不多陈述，感兴趣的同学可以自己试试)