C++版本-将就看看吧~~
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ class Solution { public: /** * * @param head ListNode类 * @param n int整型 * @return ListNode类 */ ListNode* removeNthFromEnd(ListNode* head, int n) { // write code here //如果当前节点后的第1、2...节点存在,第n个不存在,那当前节点就是要删除的 //问题是:不可能每次移动一个,就判断一次 //法1:直接遍历一次,得出总长度len,再从头开始找到倒数的第n个删除,O(n), //法2:快指针先走n步,然后同时走,快指针为空)的时候,慢指针刚好到要删除的节点O(n) //注意删除头节点或者尾节点的情况 //由于没有指明是双向链表,保存一下slow的前一个节点 ListNode* tmp= new ListNode(-1); tmp->next=head;//加个伪节点在之前 auto fast=head; auto slow=head; while(n){ fast=fast->next; n--; } //如果快指针这个时候没有为空,就可以继续 while(fast){ fast=fast->next; slow=slow->next; tmp=tmp->next; } //如果为空跳出while,判断下slow是否是首节点 if(slow==head) return head->next; //如果是尾节点 if(slow->next==nullptr){ tmp->next=nullptr; }else{ tmp->next=slow->next; } return head; } };