Leetcode-19- delete the penultimate node of the linked list (medium)

19. Delete the last of the linked list N Nodes ( secondary )

I'll give you a list , Delete the last of the linked list n Nodes , And return the head node of the list .

Advanced ： Can you try a scan implementation ？

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]

Ideas ：

Set a dummy node , its next The pointer points to the head node of the list . such , There is no need to make special judgment on the head node .

for example , In the subject , If we want to delete nodes y, We need to know the nodes y The precursor node of x, And will x Pointer to y Successor node . But because there is no precursor node in the head node , So we need to make a special judgment when deleting the head node . But if we add dummy nodes , Then the precursor of the head node is the dummy node itself , At this point, we just need to consider the general situation .

1. Two iterations ： The first traversal determines the length of the linked list L,（ set up head The node is the first node ）, Is the first L-n+1 Nodes are nodes to be deleted , The first L-n Nodes are their precursor nodes . then , The second traversal finds the second L-n Nodes , And make it next Point to l-n+2 Nodes .
2. Stack ： According to the nature of the stack , Stack all nodes , Is the first n The nodes that are out of the stack are the nodes to be deleted , When it comes out of the stack , The precursor node is stack.top() Node to , Set to temp, Make it next Point to temp->next->next The node of .
3. Double pointer ： Set double pointer i,j, send j Pointer ratio i Pointer fast n Step , be j Pointer to NULL when ,i The pointer points to the node to be deleted ; if j Pointer ratio i Pointer fast n+1 Step , be j Pointer to NULL when ,i The pointer points to the precursor node of the node to be deleted , Make it next Point to temp->next->next The node of .（ Traverse once ）

（1）C++_1

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* p = new ListNode(0,head);
        ListNode* q = head;
        int l = 0;
        while(q!=nullptr){
            l+=1;
            q = q->next;
        }
        ListNode* temp = p;
        for(int i=0;i<l-n;i++){
            temp = temp->next;
        }
        temp->next=temp->next->next;
        ListNode* res = p->next;
        delete p;
        return res;
    }
};

(2)C++_2

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* p = new ListNode(0,head);
        ListNode* q = p;
        stack<ListNode*> s;
        while(q!=nullptr){
            s.push(q);
            q=q->next;
        }
        for(int i=0;i<n;i++){
            s.pop();
        }
        ListNode* temp = s.top();
        temp->next = temp->next->next;
        ListNode* res = p->next;
        delete p;
        return res;
    }
};

(3)C++_3

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* p = new ListNode(0,head);
        ListNode* i = p;
        ListNode* j = head;
        for(int k=0;k<n;k++){
            j=j->next;
        }
        while(j!=nullptr){
            j=j->next;
            i=i->next;
        }
        i->next = i->next->next;
        ListNode* res = p->next;
        delete p;
        return res;
    }
};

(4)python_1

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        p = ListNode(0,head)
        l=0
        q = head
        while(q!=None):
            l+=1
            q=q.next
        temp = p
        for i in range(l-n):
            temp = temp.next
        temp.next=temp.next.next
        res = p.next
        del p
        return res

(5)python_2

python Available in the list Realize the function of stack

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        p = ListNode(0,head)
        s=[]
        q = p
        while(q!=None):
            s.append(q)
            q=q.next
        for i in range(n):
            s.pop()
        temp = s[-1]
        temp.next=temp.next.next
        res = p.next
        del p
        return res

(6)python_3

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        p = ListNode(0,head)
        i = p
        j = head
        for k in range(n):
            j = j.next
        while(j!=None):
            j = j.next
            i = i.next
        i.next=i.next.next
        res = p.next
        del p
        return res