LeetCode——019

/*
19. Remove Nth Node From End of List My Submissions QuestionEditorial Solution
Total Accepted: 104327 Total Submissions: 355590 Difficulty: Easy
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.

Subscribe to see which companies asked this question
*/
/*
解题思路：
1.我们要删除单链表中的一个元素（在不变动其值得情况下），我们只能是先找到它的前一个节点，然后重新连接。在这里为了防止删除的是正数第一个节点，所以我们有必要加一个临时的头结点dummy。

2.采用快慢指针的思路，去定位倒数第n个节点。两个游标指针fast,slow。先让fast走n步，然后二者同时往下走。最终slow走到要删除节点的前一个元素，而fast走向NULL。

3.执行删除操作。返回dummy->next.
*/

/**
 * 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) {

        //使用快慢指针确定倒数第n个元素
        ListNode* dummy=new ListNode(-1);
        dummy->next=head;
        ListNode* fast=head,*slow=dummy,*pre=dummy;
        for(int i=0;i<n;i++){
            fast=fast->next;
        }
        while(fast){
            fast=fast->next;
            slow=slow->next;
        }
        fast=slow->next;
        slow->next=fast->next;
        delete(fast);
        return dummy->next;

    }
};