Leetcode.19 删链表倒数第 N 个结点(栈/先后指针)

 题目链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

目录

题目描述

解析

1、栈

2、先后指针

---

 

题目描述

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]
 

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

解析

这里给出两种解法：栈、先后指针。

1、栈

        思路是，新建一个栈，遍历一遍链表，将结点压入栈。然后再依次弹出n个结点，这样就满足了删除倒数第n个元素了。注意开始时需要在原链表前面添加一个哑结点，作用是，如果头结点要被删除，那么返回哑结点的next即可，这样就可以避免报错。时间复杂度就是遍历一遍链表加上栈的一系列操作，总的是O(n)。因为开辟了一个栈，因此空间复杂度是O(n)。

/**
 * Definition for singly-linked list.
 * 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<ListNode*> s;
        ListNode* dummy = new ListNode(0, head); //在原链表最前面加一个哑结点，指向原链表的第一个结点
        ListNode* curr = dummy;
        while(curr != NULL){
            s.push(curr);
            curr = curr->next;
        }
        for(int i = 0; i < n; i++) s.pop();
        ListNode* tmp = s.top();
        tmp->next = tmp->next->next;
        ListNode* res = dummy->next; //作用是避免head也被删除时报错
        delete dummy;  
        return res;
    }
};

2、先后指针

        思路是，使用两个指针，假设链表长度为L，先使用succ指针，在链表上向右移动 n 个结点，接着再使得succ指针和pre指针一起向右移动，直到succ指针到达尾结点为止，此时pre指针一共移动了(L - n)个结点，相当于移动到倒数第n个链表位置了。总时间复杂度是O(n)，空间复杂度是O(1)，因为没有开辟新的空间。

/**
 * Definition for singly-linked list.
 * 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) {
        if(head == NULL) return NULL;
        ListNode* succ = head, *pre = head; //succ先移动，pre后移动
        for(int i = 0; i < n; i++) succ = succ->next;
        if(succ == NULL) return head->next;  //如果删除的是第一个结点，就返回第一个结点的下一个结点
        while(succ != NULL and succ->next != NULL){ //succ->next != NULL是为了防止pre指针多移动一个结点
            succ = succ->next;
            pre = pre->next;
        }
        pre->next = pre->next->next;
        return head;
    }
};