19删除节点

双指针法

struct ListNode {
    int val;
    struct ListNode *next;
};

//双指针法
struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    //建立虚拟头指针
    struct ListNode *cur = (struct ListNode *)malloc(sizeof(struct ListNode));
    cur->next = head, cur->val = 0;
    struct ListNode* first, * second;
    first = head, second = cur;
    for (int i = 1; i <= n; i++) first = first->next; //走n步

    while (first) { //同步走，使second指向想删除的节点的前一个节点
        first = first->next;
        second = second->next;
    }
    second->next = second->next->next; //使想删除的节点的前一个节点指向想删除的节点的后一个节点
    first = cur->next;//重新指向链表头节点
    free(cur);//释放内存
    return first;
}

暴力法

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    int l = 0;
    //定义虚拟头节点
    struct ListNode *cur = (struct ListNode *)malloc(sizeof(struct ListNode));
    cur->next = head, cur->val = 0;
    struct ListNode *p = head, *q;
    
    //计算链表长度
    while (p) {
        ++l;
        p = p->next;
    }
    
    p = head; //是指针重新指向头节点
    //使指针走到想删除节点的前一节点
    int k = l - n; 
    p = cur;
    while (k--) p = p->next;
    
    q = p->next; //指向想删除的节点
    p->next = q->next; //使想删除的节点的前一个节点指向想删除的节点的后一个节点
    q = cur->next; //重新指向链表头节点
    free(cur);//释放内存
    return q;
}

利用栈

栈的性质：先进后出。

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 n) {
        stack s;
        ListNode* cur = new ListNode(0, head);
        ListNode* p = cur;
        while (p) { //将全部节点地址压入栈中
            s.push(p);
            p = p->next;
        }
        while(n--) s.pop(); //删除到栈顶元素为想删除的节点的前一个节点
        p = (s.top()); 取栈顶元素
        p->next = p->next->next; //使想删除的节点的前一个节点指向想删除的节点的后一个节点
        p = cur->next;
        delete cur;
        return p;
    }
};