19.删除链表的倒数第N个节点

下面是题目

下面是题目给出的代码

/**
 * 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) {
        
    }
};

我自己做的时候，用了一种不太美观的代码搞出来了

//因为分了很多类别，我不想过细的去讨论这个代码
//但整体的思路，就是先遍历一遍取节点个数，再遍历一遍找到节点，删除
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int count = 0;
        ListNode*cur = head;
        while(cur)
        {
            count++;
            cur = cur->next;
        }
        cur = head;
        if(count==1&&n==1)
        {
            return NULL;
        }else if(n==1)
        {
            for(int i = 0;i<count-2;i++)
            {
                cur= cur->next;
            }
            cur->next = NULL;
            return head;
        }
        for(int i = 0;i<count-n;i++)
        {
            cur = cur->next;
        }
     
        if(cur->next)
        {
            ListNode *toDelete = NULL;
            toDelete = cur->next;
            cur->val = toDelete->val;
            cur->next = toDelete->next;
            delete toDelete;
        } 
        
        return head;
    }
};

下面是改良版，看这个！

//经过改良之后，会有更简单的 出现
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        //首先仍然是统计长度
        int len = 0;
        ListNode *cur = head, *toDelete = NULL;
        while(cur->next)
        {
            cur = cur->next;
            len++;
        }
        //现在 len = 总长度-1；
        cur = head;
        //这里，len+2-n 就是需要循环的次数。也就是说，n越大，需要循环次数越少
        for(int i = 0;i<len+2-n;i++)
        {
            //如果第一个节点就是要求被删除的节点
            if(len+1==n) return head->next;
            //这个代码需要画一下，就是说，如果当前节点的下一个节点是要被删除的
            //完整版就是 i+1 == len + 1 - n; 简化后，就是i == len - n;
            if(i==len-n)
            {
                toDelete = cur->next;
                cur->next = toDelete ->next;
                delete toDelete ;
                break;
            }else
            {
                cur = cur->next;
            }
        }
        return head;
    }
};

用快慢指针的方法，只需要循环一次就能办到

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        //先建立一个dummyNode 
        ListNode *dummyNode = new ListNode(0);
        //然后建立两个节点：快捷点和慢节点。
        ListNode *second = dummyNode;
        ListNode *first = dummyNode;
        dummyNode ->next = head;
        /*
        	敲桌板的东西来了
        	设 链表的节点数为len
        	我们知道，在建立了dummyNode后，从dummyNode走到NUll 需要走len+1布
        	现在，让快捷点先走n+1 步
        	然后，快慢节点同时运动，一直到快节点指向NULL时停止
        	可知：现在慢节点走了 len-n 步，也就是说，位于第len-n个节点（0节点也包含在内）
        	要知道，要删除的节点n位于的时第len-n+1个节点
        	所以说，现在只要删除慢节点后面那个节点，就大功告成了！！！！！！！！！！
            
        */
        for(int i = 0;i<n+1;i++)
        {
            first = first->next;
        }
        while(first)
        {
            first = first->next;
            second = second ->next;
        }
        ListNode *temp = second->next;
        second->next= second->next->next;
        delete temp;
        //下面其实可有可无，只是要不要保留dummyNode 的问题
        ListNode *res = dummyNode->next;
        delete dummyNode;
        return res;
    }
};