思路
双指针,同等速度,但是出发点不一样(fast比slow多走n-1步骤)
注意要考虑到前一个节点,
注意要释放节点,拒绝内存泄漏
注意要设置一个哑巴节点,使算法具有普适性
代码
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ class Solution { public: /** * * @param head ListNode类 * @param n int整型 * @return ListNode类 */ ListNode* removeNthFromEnd(ListNode* head, int n) { /* if(head==nullptr) return nullptr; // write code here // 倒数第n个节点 = 正数第k+1-n个,k为节点个数 ListNode* cur = head; int count = 0; while(cur!=nullptr){ cur = cur->next; count++; } ListNode* dum = new ListNode(0); dum->next = head; ListNode* ptr = dum; // 这样变成了删除K+2-n个指针,先找到k+2-n-1个指针 for(int i = 1; i<=count-n;i++){ ptr = ptr->next; } ListNode* nex = ptr->next; ptr->next = nex->next; free(nex); return dum->next; */ // 双指针法 ListNode* dump = new ListNode(0); dump->next = head; ListNode* slow = dump; ListNode* fast = dump; // fast指针先走n-1步 for(int i = 1; i<=n+1; i++){ fast = fast->next; } while(fast!=nullptr){ fast = fast->next; slow = slow->next; } slow->next = slow->next->next; return dump->next; } };