19. 删除链表的倒数第N个节点

[MyLinChi]

题目描述

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：

给定的 n 保证是有效的。

链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list

方案一（自己）

通过把指向各个结点的指针保存在一个vector中，然后利用数组可以被随机访问的特性来完成数据的指针的重新连接和结点的删除。
坑一：删除堆内存时用delete方法。
坑二：注意删除是头结点时的特殊情况。

/**
 * 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) {
        vector<ListNode*> list={};
        ListNode* head1 = head;
        while(head){
            list.push_back(head);
            head = head->next;
        }
        int len = list.size();
        ListNode* tmp = list[len-n]->next;
        delete list[len-n];
        if(len-1-n>=0)
            list[len-1-n]->next = tmp;
        else
            head1 = tmp;
        return head1;
    }
};

方案二（双指针）

两个指针之间隔了n-1隔元素，以同等速度向后移动，当前面的指针到达最后一个结点时停止移动。
坑：为了便于处理只有一个结点的情况，在链表前面加一个哑结点。但不懂为啥用new创建一个结构体时竟然出错了。

/**
 * 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 t(0);
        ListNode* dummy = &t;
        dummy->next = head;
        ListNode* p1 = dummy;
        ListNode* p2 = dummy;
        while(n--)p2=p2->next;
        while(p2->next){p1=p1->next;p2=p2->next;}
        ListNode* tmp = p1->next;
        p1->next = tmp->next;
        return dummy->next;
    }
};