---
tags: LeetCode,Top 100 Liked Questions
---
# 19. Remove Nth Node From End of List
https://leetcode.com/problems/remove-nth-node-from-end-of-list/
## 題目敘述
Given the head of a linked list, remove the nth node from the end of the list and return its head

Definition for singly-linked list.
  struct ListNode {
      int val;
      ListNode *next;
      ListNode() : val(0), next(nullptr) {}
      ListNode(int x) : val(x), next(nullptr) {}
      ListNode(int x, ListNode *next) : val(x), next(next) {}
 };

## Example
#### return ListNode*
Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1
Output: [1]

## 解題想法
### 1.
先記錄開頭到nth node的length
此時有2種情況
(1)刪除length=1的node -> head=head->next
(2)刪除其他node -> 將前一個node的next 指向下下一個node

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int node=0;
        ListNode* current=head;
        while(current!=NULL){
            current=current->next;
            node++;
        }
        current=head;
        int length=node-n+1;
        if(length==1){
            //to remove node in length is 1
            head=head->next;
        }
        else{
            length-=2;
            while(length>0){//current is the node before need to remove 
                length--;
                current=current->next;
            }
            current->next=current->next->next;
        }
        return head;
    }
};

時間複雜度為O(N)

### 2.Turtle-Hare alogrithm
已知nth node from the end必定距離null n個節點
於是利用2個pointer 2者距離n
當前面pointer到達null 後面pointer的next指向下下一個即完成

class Solution {
public:
   ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* start = new ListNode();
        start->next = head;
        
        ListNode* fast = start;
        ListNode* slow = start;
        
        for(int i=1;i<=n;i++){
            fast = fast->next;
        }
        while(fast->next != NULL){
            cout<<slow->val<<" "<<fast->val;
            slow = slow->next;
            fast = fast->next;
        }
        
        slow->next = slow->next->next;
        return start->next;
    }
};

時間複雜度為O(N)