Leetcode 19. delete the penultimate node of the linked list [knowledge points: speed pointer, recursion, stack]

subject

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

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 list is sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

Advanced ： Can you try a scan implementation ？

source ： Power button （LeetCode）
link ：leetcode 19. Delete the last of the linked list N Nodes
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Problem solving

Method 1 ： Follow the meaning of the topic , Calculate the length of the list

First traverse the entire linked list to calculate the length of the linked list L, Then traverse the linked list to the previous node of the node to be deleted ： The deleted node is L-n+1 individual , Traversing L-n stop

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */


struct ListNode* removeNthFromEnd(struct ListNode* head, int n)
{
    
    struct ListNode dummyHead;
    dummyHead.next = head;
    dummyHead.val = 0; // Store the number of linked list elements 
    struct ListNode* p;

    for(p=head;p;p=p->next,dummyHead.val++);

    int i = 0;
    for(p=&dummyHead;i < dummyHead.val-n;p=p->next,i++);

    struct ListNode* temp = p->next;
    p->next = temp->next;
    free(temp);

    return dummyHead.next;
}

Method 2 ： Front and rear double pointers （ Optimal solution of this problem ）（ Just traverse once ）

Double pointer p,q Initialization points to the virtual header ; Front pointer q Go ahead , When p,q Interval between n Node time ,p,q All walk back at the same time ; until q End of traversal , here p It refers to the previous node that needs to be deleted ;

struct ListNode* removeNthFromEnd(struct ListNode* head, int n)
{
    
    struct ListNode dummyHead;
    dummyHead.next = head;
    
    struct ListNode *front,*behind;
    front = behind = &dummyHead;

    int TheIntervalBetweenTwoPointers = -1;
    while(behind){
    

        if(TheIntervalBetweenTwoPointers != n){
    

            behind = behind->next;
            TheIntervalBetweenTwoPointers++;
        }else{
    

            front = front->next;
            behind = behind->next;
        }
    }

    struct ListNode* temp = front->next;
    front->next = temp->next;
    free(temp);

    return dummyHead.next;
}

Method 3 ： Stack

Because it is to be deleted, press the reciprocal , It's easy to think of stacks , Last in, first out , Put the whole list on the stack at one time , Further stack Find the front node of the node that needs to be deleted ;

Array stack ：

typedef struct _Stack{
    
    struct ListNode* A[31];
    int Top;
}Stack;

void Push( Stack* S,struct ListNode* p )
{
    
    S->Top++;
    S->A[S->Top] = p;
}

struct ListNode* Pop( Stack* S )
{
    
    return S->A[S->Top--];
}

struct ListNode* removeNthFromEnd(struct ListNode* head, int n)
{
    
    struct ListNode dummyHead;
    dummyHead.next = head;
    
    Stack* S = malloc(sizeof(Stack));
    S->Top = -1;

    struct ListNode* p = &dummyHead;
    while(p){
    

        Push( S,p );
        p = p->next;
    }

    while(n--){
    
        Pop( S );
    }

    p = Pop( S );
    struct ListNode* temp = p->next;
    p->next = temp->next;
    free(temp);
    free( S );

    return dummyHead.next;
}

Chain stack ：

Method four ： recursive

Another way to count backwards is recursion , In fact, linked lists are very suitable for recursion , For example, the application of recursion in binary tree

struct ListNode* removeNthFromEnd(struct ListNode* head, int n)
{
    
    static int K = 0;

    if(head->next){
    
        head->next = removeNthFromEnd( head->next,n );
    }

    K++;

    if(K == n){
    
        struct ListNode* temp = head->next;
        free(head);
        return temp;
    }else{
    
        return head;
    }
}

The test case ：[1] 1 When tested separately , No problem ; But it just couldn't pass when submitting , strange

Reference to others java Code ：

class Solution {
    
    int i=0;
    public ListNode removeNthFromEnd(ListNode head, int n) {
    
        if(head.next!=null)
            head.next=removeNthFromEnd(head.next,n);
        i++;
        if(i==n)
            return head.next;
        else return head;
    }
}