Remove Nth Node From End of List

## Description

Given a linked list, remove the nth node from the end of list and return its head.

``````For 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. Try to do this in one pass.

## Solution

### 1. 使用循环

1. 定义 `p1 = p2 = head`

3. 此时p1与p2相差n个结点。让p1、p2同时前进，知道p1指向尾结点，此时p2指向倒数第n+1个结点

4. 删除`p2.Next`(即倒数第n个结点)

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 `````` ``````/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func removeNthFromEnd(head *ListNode, n int) *ListNode { p1 := head // point the next Nth node for i := 0; i < n; i++ { p1 = p1.Next } if p1 == nil { // It's removing the first node from begin return head.Next } p2 := head // p2 is now n step behind p1 // let p1 point to the 1st node from end // so p2 is pointing to the (n+1)th node from end for p1.Next != nil { p1 = p1.Next p2 = p2.Next } // now remove the Nth node from begin p2.Next = p2.Next.Next return head }``````

### 2. 使用递归

1. 使用递归一直向后查找，直到最后一个结点(`head.Next == nil`)。此时递归结束，开始返回：当前结点指针和0。相当于将最后一个结点标记为0

3. 递归完全返回后，函数`removeNthFromEnd`里的 index 如果为0，则表示parent指向第倒数n+1；不为0则没找到，原因是要删除结点的是正向第一个。
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 `````` ``````/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func removeNthFromEnd(head *ListNode, n int) *ListNode { parent, index := search(head, n) if index != n { // It must be removing the first node from begin return head.Next } // remove the child node parent.Next = parent.Next.Next return head } func search(head *ListNode, n int) (*ListNode, int) { if head.Next == nil { // mark last node's index as 0 return head, 0 } p, index := search(head.Next, n) if index == n { // so index n is the (n+1)th node from the end // it's the parent of the node which we want to remove return p, index } return head, index + 1 }``````