# 【LeetCode】 19. Remove Nth Node From End of List

## Description
> Given a linked list, remove the n-th node from the end of list and return its head.

> 給一個linked list，移除掉從後面數過來第n個數字並回傳list的起點。

## 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.

## Solution

* linked-list的題目，兩種解法，一種需要跑兩次list，一種只需要跑一次。
* 第一種：先得到list的長度，就可以知道由正向去找要刪掉哪一個數字了。
* 第二種：用兩個指標，先讓第一個跑`n`步，接著兩個一起跑，當第一個到底的時候，第二個所指的就是要移除的數字了。

### Code
* 解法一：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* temp = head;
        int s=0;
        for(;temp;s++)
            temp=temp->next;
        
        n=s-n;
        temp = head;
        if(n==0) return head->next;
        
        for(int i=0;i<n-1;i++)
            temp = temp->next;
        
        if(temp->next)
            temp->next = temp->next->next;
        
        return head;
    }
};

* 解法二：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* first = head;
        for(int i=0;i<n;i++)
            first=first->next;
        
        if(!first)
            return head->next;
        
        ListNode* second = head;
        for(;first->next;first=first->next)
            second=second->next;
        
        if(second->next)
            second->next=second->next->next;
        
        return head;
    }
};

###### tags: `LeetCode` `C++`