leetcode19笔记--删除链表的倒数第N个节点

这题在leetcode中是中等难度的题目。难点在于找到倒数第N个节点。
即给定一个链表如下：

若要找到倒数第N个节点，首先计算出链表的大小(size)才能找到倒数第二个节点所在的位置。可以使用while循环从表头开始向后计算，直到表尾NULL结束为止(一般链表最后一个节点默认指向NULL)。代码如下：

        int count = 0;
        ListNode* tmp = head;
        while(tmp!=NULL)
        {
            ++count;
            tmp=tmp->next;
        }

在得到链表的大小后，就能找到我们需要删除的节点。我们用变量del来表示该节点所处的位置，del = count - N。在删除该节点之后，要返回一个由剩余节点组成的完整的链表，因此要将删除节点的前一个节点找到。这两个节点可以在一个while循环中找到。

        tmp = head;
        ListNode* tmp1 = head;
        while(del!=0)
        {
            if(del==1)
                tmp1 = tmp;
            --del;
            tmp = tmp->next;
        }

tmp指向要删除的节点，tmp1指向删除节点的前一个节点。
要删除tmp指向的节点，我们只需要将tmp1节点指向tmp->next即可。

tmp1->next = tmp->next;

完整代码如下：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int count = 0;
        ListNode* tmp = head;
        while(tmp!=NULL)
        {
            ++count;
            tmp=tmp->next;
        }
        if(count==1)
        {
            head=NULL;
            return head;
        }
        int del = count - n;
        if(del==0)
        {
            head = head->next;
            return head;
        }
        tmp = head;
        ListNode* tmp1 = head;
        while(del!=0)
        {
            if(del==1)
                tmp1 = tmp;
            --del;
            tmp = tmp->next;
        }
        tmp1->next = tmp->next;
        return head;
    }
};