Leetcode | Remove Nth Node From End of List

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.

Method I

没去想快慢指针的做法。而是用了一个vector以便可以根据下标定位到具体的节点。

这里为了删除节点方便，用了指针的指针，ListNode**，这样直接修改当前位置为下一个位置就行了，不管它是不是head。

注意的是，在循环里面，临时变量p必须也是ListNode**的类型，不能是ListNode*，后者会造成&p得到的是临时地址；

 1 class Solution {
 2 public:
 3     ListNode *removeNthFromEnd(ListNode *head, int n) {
 4         if (head == NULL) return NULL;
 5         vector<ListNode**> nodes;
 6         ListNode** p = &head;
 7         while (*p != NULL) {
 8             nodes.push_back(p);
 9             p = &((*p)->next);
10         }
11         *nodes[nodes.size() - n] = (*nodes[nodes.size() - n])->next;
12         return head;
13     }
14 };

Method II

用两个指针，第一个指针先跑了n次。然后第二个再跑。这样当第一个指针跑到头时，第二个指针就跑到从后往前数第n个指针了。

 1 class Solution {
 2 public:
 3     ListNode *removeNthFromEnd(ListNode *head, int n) {
 4         if (head == NULL) return NULL;
 5         ListNode** p1 = &head, **p2 = &head;
 6         
 7         for (int i = 0; i < n; ++i) {
 8             if (!*p1) return NULL;
 9             p1 = &((*p1)->next);
10         }
11         
12         while (*p1) {
13             p2 = &((*p2)->next);
14             p1 = &((*p1)->next);
15         }
16         *p2 = (*p2)->next;
17         
18         return head;
19     }
20 };

果然这些链表类的题要一起做，不然都想不到好办法。。。