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

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

所以快慢指针只是减少了遍历一遍链表长度实质上就是用fast来代替长度罢了………………

还不如自己写一遍傻的暴力

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead=new ListNode(0);
        dummyHead->next=head;
        ListNode* fast=dummyHead;
        ListNode* slow=dummyHead;
        while(n&&fast->next!=NULL){
            fast=fast->next;
            n--;
        }
        fast=fast->next;
        while(fast!=NULL){
            fast=fast->next;
            slow=slow->next;
        }
        slow->next=slow->next->next;
        return dummyHead->next;
    }

};

暴力

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead=new ListNode(0);
        dummyHead->next=head;
        int length=0;
        while(head!=NULL){
            length++;
            head=head->next;
        }
        ListNode* cur=dummyHead;
        for(int i = 1 ;i<=length-n;i++){
            cur=cur->next;
        }
        cur->next=cur->next->next;
        return dummyHead->next;
    }

};