Problem description

Give you a linked list, delete the penultimate node of the linked list, and return the head node of the linked list. Advanced: can you try using one scan?

• Example 1:
  Input: head = [1,2,3,4,5], n = 2
  Output: [1,2,3,5]
  

• Example 2:
  Input: head = [1], n = 1
  Output: []

• Example 3:
  Input: head = [1,2], n = 1
  Output: [1]

• Tips:
  The number of nodes in the linked list is sz
  1 <= sz <= 30
  0 <= Node.val <= 100
  1 <= n <= sz

Solution idea

When operating the linked list, a common technique is to add a dummy node whose \ textit{next}next pointer points to the head node of the linked list. In this way, we do not need to make special judgment on the head node.
For example, in this problem, if we want to delete node yy, we need to know the predecessor node xx of node yy and point the pointer of xx to the successor node of yy. However, since there is no precursor node in the head node, we need to make special judgment when deleting the head node. However, if we add a dummy node, the precursor node of the head node is the dummy node itself. At this time, we only need to consider the general situation.
In particular, in some languages, memory needs to be managed by itself. Therefore, in the actual interview, we need to actively communicate with the interviewer to reach an agreement on the question of "whether we need to release the space corresponding to the deleted node".

The most intuitive solution is to traverse the linked list to get the table length, then know the penultimate N is the number of nodes, and then traverse it again to delete it.
A better solution is to use the fast and slow pointers: set up the fast and slow pointers. The fast pointer takes N steps first, and then the fast and slow pointers go together. When the fast pointer reaches the end, the slow pointer points to the penultimate node.
Pay attention to the handling of two unexpected situations: empty table and N-ratio table. The following code can avoid these two problems.

code implementation

class Solution {
   public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* first = head;
        ListNode* second = dummy;
        for (int i = 0; i < n; ++i) {
            first = first->next;
        }
        while (first != nullptr) {
            first = first->next;
            second = second->next;
        }
        ListNode* temp = second->next;
        second->next = second->next->next;
        ListNode* ret = dummy->next;
        delete temp;
        delete dummy;
        return ret;
    }
};

Test code

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) {}
};

/*Debug function*/
ListNode* makeAList(std::vector<int>& array);
void printList(ListNode* l);
void deleteAList(ListNode* head);

int main(int argc, char* argv[]) {
    Solution* s0 = new Solution();

    std::vector<int> v1 = {1, 2, 3, 4, 5};
    ListNode* head = makeAList(v1);
    s0->removeNthFromEnd(head, 2);

    printList(head);

    deleteAList(head);
    delete (s0);
    s0 = nullptr;
    head = nullptr;
    return 0;
}

ListNode* makeAList(std::vector<int>& array) {
    ListNode* head = nullptr;
    ListNode* tail = nullptr;
    for (std::vector<int>::iterator it = array.begin(); it != array.end();
         ++it) {
        if (head == nullptr) {
            head = tail = new ListNode(*it);
        } else {
            tail->next = new ListNode(*it);
            tail = tail->next;
        }
    }

    if (tail != nullptr) {
        tail->next = nullptr;
    }
    return head;
}

void printList(ListNode* l) {
    while (l != nullptr) {
        std::cout << l->val << std::endl;
        l = l->next;
    }
    return;
}

void deleteAList(ListNode* head) {
    ListNode* p;
    while (head != nullptr) {
        p = head;
        head = head->next;
        delete (p);
    }
}

Harvest and doubt

Pay attention to the critical situation of the linked list problem.

Original title address

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