Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Delete the NTH node from the list

Topic describes

Given a linked list, delete the NTH ** node from the bottom of the list and return the head of the list.

Advanced: Can you try using a scan implementation?

Example 1:

Input: head = [1,2,3,4,5], n = 2Copy the code

Example 2:

Input: head = [1], n = 1 output: []Copy the code

Example 3:

Input: head = [1,2], n = 1Copy the code

The illustration

Double pointer: Use fast and slow Pointers to solve this problem. The fast pointer takes n steps before the slow pointer (to set the virtual head node), and then walks backwards together. When the fast pointer points to the last node, the next node that the slow pointer points to is the node to be deleted.

CODE

#include <iostream>

using namespace std;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int v) : val(v), next(nullptr) {};ListNode(int v, ListNode *next) : val(v), next(next){};
};

class Solution
{
public:
    ListNode *removeNthFromEnd(ListNode *head, int n)
    {
        // Use a virtual head node to delete the head node
        ListNode *dummpy = new ListNode(0, head);
        // The slow pointer points to the precursor node of the point to be deleted
        ListNode *pre = dummpy;
        // Fast pointer to the node being traversed
        ListNode *cur = pre->next;
        // The fast pointer takes n steps first
        while (n--)
        {
            cur = cur->next;
        }
        // Iterate over nodes. When the fast pointer points to the last node, all nodes are traversed
        // The slow pointer now points to the node before the point to be cut
        while(cur ! =nullptr)
        {
            cur = cur->next;
            pre = pre->next;
        }
        // Delete a node
        ListNode *tmp = pre->next;
        pre->next = tmp->next;
        delete tmp;

        // return the head node
        return dummpy->next;
    }

    void printListNode(ListNode *head)
    {
        ListNode *cur = head;
        while (cur)
        {
            cout << cur->val << ""; cur = cur->next; } cout << endl; }};int main(a)
{
    // Test the code
    ListNode *head = new ListNode(1);
    ListNode *p1 = new ListNode(2);
    ListNode *p2 = new ListNode(3);
    ListNode *p3 = new ListNode(4);
    head->next = p1;
    p1->next = p2;
    p2->next = p3;

    Solution solu;
    ListNode *newHead = solu.removeNthFromEnd(head, 4);
    solu.printListNode(newHead);

    return 0;
}
Copy the code