题目：

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

例子：

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.

注释：

Given n will always be valid.

额外要求：

Could you do this in one pass?

思路：

根据提示，可以用两个指针，first指针标记链表的末尾，second指针标记链表末尾之前n位的链表。然后当链表到了末尾后，将second指针的下一位连到second指针的上一位。

知识点：

  • second指针要在first指针之前的n+1位，因为这是单链表，没有second->prev的指针，所以在去除链表倒数第n位的时候，只能用second->next = second->next->next。
  • 所有的临界情况都要考虑全面，比如只有一个元素的时候input: [1] 1
  • 出于上面一条的原因，first和second指针的起点要设置在head之前，可以省去判断。
  • C++的指针要用->运算符
  • 复习C++的constructor：如果需要返回的是一个指针，要用ListNode* first = new ListNode(0)
  • 函数的输入参数中，链表头是head指针，指向的是一个数值为val，下一位是next的ListNode，如果被去掉的是链表头，那head依然还是会指向这个node。因为我们是用second->next = second->next->next来去掉节点的，所以改变的是second->next，没有改变head，即使second->next是从head开始的，但second只是个指针变量，存储的是当前指向的地址。
  • 出于上面一条的原因，可以用一个dummy变量存储初始点的地址，最后返回dummy->next

代码：

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
/**
 * 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* ptr1 = new ListNode(0);
        ListNode* ptr2 = new ListNode(0);
        ListNode* dummy = ptr1;
        ptr1->next = head;
        ptr2->next = head;
        for(int i =0; i<n; i++){
            ptr2 = ptr2->next;
        }
        while(ptr2->next!=NULL){
            ptr2 = ptr2->next;
            ptr1 = ptr1->next;
        }
        ptr1->next = ptr1->next->next;
        
        return dummy->next;
    }
     
};