Remove Nth Node From End of List

编号 : 19      
难度 : <font color="orange">Medium</font>

# 题目 :  
>Given a linked list, remove the n-th node from the end of list and return its head.
>
>**Example**:
>
>>Given linked list: **1->2->3->4->5**, and ***n = 2***.
>>
>>After removing the second node from the end, the linked list becomes **1->2->3->5**.
>
>**Note**:
>
>Given n will always be valid.
>
>**Follow up**:
>
>Could you do this in one pass?
>

# 解 :  
```Cpp
/**
 * 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) {
        /* 令p1 = head，即第1个节点 */
        auto p1 = head;
        
        /* 令p2 = list[n]，即第n+1个node */
        auto p2 = head;
        for(int i = 0; i < n && p2 != nullptr; i++)
        {
            p2 = p2->next;
        }
        
        /* 第n+1个节点为nullptr，不存在
         * 说明一共只有n个节点
         * 要删除的是第一个节点
         * 即要删除head 
         */
        if(p2 == nullptr)
        {
            auto temp = head;
            head = head->next;
            delete temp;
        }
        else
        {
            /* p1和p2一起向后移动，保证距离不变，直到p2指向最后一个节点 */
            for(; p2->next != nullptr;)
            {
                p2 = p2->next;
                p1 = p1->next;
            }

            /* 删除p1后面的node*/
            auto temp = p1->next;
            p1->next = p1->next->next;
            delete temp;
        }
        
        /* 返回 */
        return head;
    }
};
```

# 分析 :  
这道题给出一个链表和一个整数n，要求删除链表的**倒数第n**个节点后返回。解法很简单，令`p1`和`p2`之间的距离为n（这里可能有歧义，采用`node[0]`和`node[1]`之间的距离是1的说法），这样一来当`p2`指向链表最后一个节点的时候，`p1`指向倒数第(n+1)个节点，即**`p1`是要删除的节点的钱一个节点**，删除`p1`后面的节点即可。

> 由于题目给的是单向链表，只有`next`指针，要删除一个节点，必须通过它的前一个节点来进行。

这里有一种特殊情况，如果要删除的节点恰好是第一个节点，没有办法让`p1`指向第一个节点的前一个节点。在上述代码中，这种情况会让`p2`初始化的时候为`nullptr`，判断这个条件然后删除第一个节点即可。

> 题目中已经说明输入的n一定是合法的，所以不需要判断。