> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/leetcode/19.-remove-nth-node-from-end-of-list-medium.md).

# 19. Remove Nth Node From End of List

## 1.問題

* 給予一個list, 刪除倒數第n個node

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LIZfYG3WqVkWWMmk0Nu%2F-LI_05P6nmu5c8pVWAbI%2F2018072901.jpg?alt=media\&token=07747aa4-68cc-4f56-8fac-ece2b9797af5)

## 2.想法

* 1.用traversal計算list有多長
* 2.刪除node
  * 需要兩個node: current, previous,分別指向目標及目標的前一個node
  * 將current移動到目標
  * 刪除node

## 3.程式碼

```
/**
 * 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) {
        ListNode *current = head;
        ListNode *previous = 0;
        if (!head->next && n == 1) {
            return NULL;
        }
        //Count the list
        int cnt = 0;
        while(current) {
            cnt++;
            current = current->next;
        }
        
        //Find the target
        current = head;
        int index = 0;
        while(current && cnt - n != index) {
            index++;
            previous = current;
            current = current->next;
        }
        
        //Delete node
        if (!previous) {
            //If the target is the head
            head = current->next;
        } else {
            //If the target is not the head
            previous->next = current->next;
        }
        
        current = 0;
        return head;
    }
};
```

## 4.Performance

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LIZfYG3WqVkWWMmk0Nu%2F-LI_07r7WXC4_uEvlMcl%2F2018072902.jpg?alt=media\&token=bb9c963d-e9d5-481d-8412-0473894a431a)