Leetcode面试算法题（Golang版）

#### 19.Remove Nth Node From End of List Given a linked list, remove the *n*th 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. #### 思路 删除单链表中节点 `node`，需要找到其前驱节点 `preNode`，再执行删除： `preNode.Next = preNode.Next.Next` 题中删除倒数第 n 个节点，只需找到倒数第 n+1 个节点即可 ##### 思路1 第一次遍历链表算出节点总数 N，计算倒数第 n+1 个节点的位置，第二次遍历找到这个前驱节点，执行删除。 时间复杂度 O(N)：遍历链表的总时间是 `N + N - n` 空间复杂度 O(1)：运算临时占用的空间大小固定 ##### 思路2 设置两个指针 cur、pre 初始位置如下，间隔 n 个节点，遍历链表当 cur 达到尾部时，pre 正是倒数第 n+1 个节点  时间复杂度 O(N)：比起思路一要少一次遍历，总时间为 `N` 空间复杂度 O(1)