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

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;

    }
};