leetcode：19. Delete the penultimate node of the linked list

Title source

• leetcode：19. Delete the last of the linked list N Nodes

title

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 k) {
    

        return head;
    }
};

Speed pointer

Test parameters first ： If the linked list is empty or K Less than 1, here , Invalid parameter , Go straight back NULL.

Then make it clear , If you want to delete a node of the linked list , In fact, you need to find the previous node to delete , So we can use Speed pointer Find the node at the specified location

We can imagine that we have two pointers p and q Words , When q At the end of NULL,p And q The number of elements separated is n when , Then delete it p The next pointer of is done .

• Set the virtual node dummyHead Point to head
• Set double pointer p and q, Initially, they all point to virtual nodes dummyHead
• Move q, until p And q The number of elements separated is n
• Move at the same time p And q, until q Point to NULL
• take p The next node of points to the next node

class Solution {
    

public:
    ListNode* removeNthFromEnd(ListNode* head, int k) {
    
        if(head == nullptr || k < 0){
    
            return head;
        }
        
        ListNode *dummyHead = new ListNode(0);
        dummyHead->next = head;
        
        
        ListNode *slow = dummyHead;
        ListNode *fast = dummyHead;
        for (int i = 0; i < k + 1; ++i) {
    
            fast = fast->next;
        }
        while (fast){
    
            fast = fast->next;
            slow = slow->next;
        }
        
        ListNode *delNode = slow->next;
        slow->next = delNode->next;
        delete delNode;
        
        ListNode* ret = dummyHead->next;
        delete dummyHead;
        
        return ret;
    }
};